인프런 커뮤니티 질문&답변

안녕하세요. 결론부터 말하자면 1-5문제 오답인데요

선생님께서 푸신 풀이와는 좀 다른 방식으로 풀었습니다.

저는 구간이 아니라 쌩으로 전체 시간 (N)을 dy로 놓고 풀었습니다. = (time_)

=> dy는 해당 시간까지의 최대효율값을 넣고있습니다.

[1] 일들을 끝나는 시간으로 정렬해서 그 순서대로 진행하는건 동일하구요.

[2] dy 배열에서 해당 일의 시작 시간 - R (쉬는시간) 부터

0번째 시간까지 한 일 중에 가장 큰 값에다 해당 일의 효율을 더하는 식으로 진행했습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int time_[1000001]; //dy***

struct my{
	int a,b,c;
	my(int a, int b, int c){
		this->a=a; //시작 시간
		this->b=b; //끝나는 시간
		this->c=c; //효율
	}
	
	bool operator<(const my& other)const{
		return b<other.b;
	}
	
};

int main() {
	int max_=0;
	int N,M,R; //총 시간, 일 개수, 휴식시간 
	vector<my> arr;
	
        ...
	
	//DP
	sort(arr.begin(), arr.end());
	for(int i=0; i< arr.size(); i++){ //일의 갯수 
		int val;
		if(arr[i].a - R >=1){
			//time의 1번째부터  arr[i].a - R번째까지 수 중에... 
			//가장 큰 값을 찾아서 더하여 넣음
			int maxtmp=0;
			for(int j=0; j<=arr[i].a-R; j++){
				if(maxtmp < time_[j]) maxtmp = time_[j];
			}
			val = maxtmp + arr[i].c;
			
		}
		else{
			val = arr[i].c;
		}
		
                //할 수 있는 일이 없으므로                   
		//다음 일정이 끝나기 전 까지 같은 값 넣기 
		int j = arr[i].b;
		time_[j]=val;
		
		while( i+1!=arr.size() && j<arr[i+1].b){
			time_[j]=val;			
			j++;			
		}
		//최대값 찾기
		if(val > max_) max_ = val;
	}
	
	cout<<max_;

	return 0;
}

이렇게 풀다가 오답이 나왔습니다. 결과는 케이스 1만 오답이고 나머지 2345는 정답인데

• 정답은 83인데 제 코드는 81이 나옵니다

큰 입력에 대해서는 정답인게 케이스 1에 뭔가 반례가 있어서 틀린 것 같은데 모르겠습니다...

이전 단계 강의에서 늘상 하던 방식으로 걸리는 시간을 배열로 놓은거라 방법 자체는 맞는 것 같은데 이유를 모르겠습니다. 도와주세요