백준 14501번: 퇴사 (dp)

[문제 링크]

14501번: 퇴사

---

지난번에 완전탐색으로 한번 풀었던 문제였는데 이번에 동적 계획법을 사용하여 다시 풀게되었다.

 

아래에서 위로 탐색하는 알고리즘은 금방 생각해냈지만, 위에서 아래로 탐색하여 정답을 얻어내는 알고리즘을 생각하다가 이틀이나 날려먹었다.....

 

일단은 아래에서 위로 재귀호출을 통해 탐색하는 방식으로 문제를 해결하였다.

이 문제의 핵심은 해당 일에 상담을 했을 때 얻는 최대이익과 상담을 하지 않았을 때 얻는 최대이익 중 더 큰 값을 선택한다는 것에 있다.

 

따라서 점화식은 다음과 같다.

dp(N) = max(dp(N+1), dp(N+T[N]) + P[N]);

 

위 점화식을 알고리즘으로 구현하면 원하는 결과를 얻을 수 있다.

---

 

#include <iostream>
using namespace std;

const int INF = 987654321;
int N, T[16], P[16], memo[16];
inline int max(int a, int b) { return a > b ? a : b; }

int brute(int start, int pay)
{
	int ret = pay;
	for (int i = start; i < N; i++)
	{
		int next = i + T[i];
		if (next > N) continue;
		ret = max(ret, brute(next, pay + P[i]));
	}
	return ret;
}

int Topdown(int start)
{
	if (start >= N) return start == N ? 0 : -INF;

	int& ret = memo[start];
	if (ret != 0) return ret;

	return ret = max(Topdown(start + 1), Topdown(start + T[start]) + P[start]);
}

int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> T[i] >> P[i];

	// brute-force
	cout << brute(0, 0) << endl;

	// top-down
	cout << Topdown(0) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 68 day