BOJ 14501, 15486 : 퇴사, 퇴사 2

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/14501

www.acmicpc.net/problem/15486

 

 

퇴사 1의 경우는 완전 탐색으로 풀 수 있지만,

퇴사 2는 N이 매우 크므로, 다이나믹 프로그래밍, 메모이제이션(memoization)으로 풀어야 한다.

 

DP[i] = i일 전까지의 최대 이익 이라고 정의를 하자.

 

i일에 일을 수행하지 않으면,

DP[i + 1] = DP[i]와 기존 memoization의 값 중 큰 값이 된다.

 

i일에 일을 수행한다면,

i일 전까지의 최대 이익인 DP[i]와 i일에 받을 보수 P[i]를 더한 값 vs 기존 memoization의 값 중 큰 값.

즉, DP[i + T[i]] = DP[i] + P[i] 와 DP[i + T[i]] 중 큰 값을 선택하면 된다.

#include <stdio.h>

#define MAX (1500000 + 50000)

int N;
int T[MAX];
int P[MAX];
int DP[MAX];

int maxVal(int a, int b)
{
	return (a > b) ? a : b;
}

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

	for (int i = 0; i < N;i++) scanf("%d %d", &T[i], &P[i]);

	for (int i = 0; i < N;i++)
	{
    	DP[i + 1] = maxVal(DP[i], DP[i + 1]);
		DP[i + T[i]] = maxVal(DP[i + T[i]], DP[i] + P[i]);
	}

	printf("%d\n", DP[N]);

	return 0;
}