백준 14501 퇴사

백준 14501 퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

퇴사 문제이다. 각각의 걸리는 시간 만큼 일은 못하지만 그 사이에서 적절한 선택을 통해 최대의 수익을 올려야하는 문제이다. 이 문제를 풀면서 어려웠던 점은 다음 경우의 수를 선택안하고 다다음의 경우를 선택하여 최대의 수익을 올릴 수 있었다. 

 

주의할 점

1. 무조건 다음 점이 아니라 다다음 점을 선택해도 최대가 될 수 있다는 점
 1번을 해결하기 위해서 현재 위치에서 진행되는 시간을 더한 것 부터 최대 가능 시간까지 반복문을 돌렸다. 

현재 위치 + 현재 업무가 걸리는 시간 <= N 까지 

 

현재는 이런 방법이 N이 1000개라 가능하지만 다른 문제의 경우 시간 초과가 날 방법일 것 같다. 

 

2. 전체 요일을 넘어서면 일을 할 수 없는 점

 

마지막 날의 경우 단 걸리는 시간이 1이 되어야만 문제를 해결할 수 있다. 따라서 아래와 같은 조건문을 만들어 주었다. 

if(i + map[i].first <= N + 1)

 

dp를 재활용하는 것은 현재 위치에서 다음으로 가는 값을 더해준 것과 다음의 dp 값 중 큰 값을 dp에 다시 저장해주었다. 

dp[i] = max(dp[i], map[i].second + value);
getMaxValue(i, map[i].first, dp[i]);

 

전체 코드

#include <cstdio>
#include <algorithm>

using namespace std;

int N;
int dp[1002];
pair<int, int> map[1002];

void getMaxValue(int now, int time, int value){
	for(int i = now + time; i <= N; i++){
		if(i + map[i].first <= N + 1){
			dp[i] = max(dp[i], map[i].second + value);
			getMaxValue(i, map[i].first, dp[i]);
		}
	}
}

int main(){
	int time, value;
	scanf("%d", &N);

	for(int i = 1; i <= N; i++){
		scanf("%d %d", &time, &value);
		map[i].first = time;
		map[i].second = value;
	}
	
	for(int i = 1; i <= N; i++){
		if(i + map[i].first <= N + 1)
			dp[i] = max(dp[i], map[i].second);
		getMaxValue(i, map[i].first, map[i].second);
	}

	printf("%d", *max_element(dp, dp+N+1));
}