삼성 코딩테스트 기출_(백준)퇴사

난이도 ★☆☆

 

문제출처

https://www.acmicpc.net/problem/14501

14501번: 퇴사

포인트

1. dp 정의

d[i][0] = i일에 상담을 하지 않는 경우 얻을 수 있는 이익의 최댓값

d[i][1] = i일에 상담을 하는 경우 얻을 수 있는 이익의 최댓값

 

2. dp 초기값

d[1][0], d[1][1]

(중요) d[1][0]은 0이지만, d[1][1]은 P[1]이 아니다. 만약 T[1]이 N의 범위를 벗어난다면, 첫째 날에도 상담이 불가능하기 때문이다. 따라서, if문을 통해, T[1]이 N의 범위를 벗어나지 않는 경우에만 d[1][1]=P[1]로 설정하고 그 외의 경우는 0으로 초기화한다.

 

3. 점화식

d[i][0]=max(d[i-1][0], d[i-1][1])

 : i일째에 상담을 하지 않을 경우, 얻을 수 있는 최댓값은 i-1째까지의 최댓값과 같다.

d[i][1]

 : 일단, i일에는 상담을 하기 때문에 P[i]만큼의 이익을 더해주는 작업이 필요하다. 그런 후, i일 전까지의 모든 날을 순회하며(j=(1부터 i-1)), d[j][1]의 최댓값을 찾아 넣어준다. 단, 여기에서 j+T[j]가 i보다 크면 안된다는 것을 주의한다.(i일에 상담을 할 수 있어야 하기 때문)

 

정답코드

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int T[20];
int P[20];
int d[20][2];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> T[i] >> P[i];
	}

	d[1][0] = 0;
	if (T[1] <= N) {
		d[1][1] = P[1];
	}
	else d[1][1] = 0;

	for (int i = 2; i <= N; i++) {
		d[i][0] = max(d[i - 1][0], d[i - 1][1]);
		if (T[i] + i <= N+1) {
			for (int j = 1; j < i; j++) {
				if (T[j] + j <= i) {
					if(d[i][1]<d[j][1]) d[i][1] = d[j][1];
				}
			}
			d[i][1] += P[i];
		}
		else d[i][1] = 0;
	}

	int ans = max(d[N][0], d[N][1]);

	cout << ans << endl;
	
	return 0;
}