[BOJ 14728] 벼락치기

이진중·2022년 5월 16일

알고리즘

목록 보기

14/76

다이나믹프로그래밍의 가장 기본이 되는 원리이다.

한문제에 대한 해가 최적이면 그 문제를 이루는 부분문제들의 해도 최적이다.

a -> b -> d로가는 최적의 길이 Jab+Jbd 이면
b -> d로가는 최적의 길은 Jbd 라는것이다.

따라서 큰 문제를 작게 쪼개서 최적의 해를 가지고 큰문제의 최적의 해를 구하는것이다.

위 문제에서 단원들을 하나씩 추가해가면서 어느 t 시점에 최적의 점수를 채워나가면서
결국 구하고자하는 특정 t시점에서의 최적의 점수를 구하면된다.

i번째 단원을 추가하지 않은경우 (Wi > w) i번째 단원을 추가한경우 (else)

dp[t]=s // t시간에 대한 최적의 점수

	for (int i = 0; i < N; i++)
	{
		cin >> k >> s;

		for (int j = T; j >= k; j--)
		{
			dp[j] = max(dp[j], dp[j - k] + s);
		}
	}

아래는 디버깅 결과이다.

중복을 허락하면 안된다. 따라서 dp를 뒤에서 부터 채워야한다 즉.

	for (int i = 0; i < N; i++)
	{
		cin >> k >> s;

		for (int j = k; j <= T; j++)
		{
			dp[j] = max(dp[j], dp[j - k] + s);
		}
	}

이렇게 앞에서 부터 T이하까지 채우게 되면

이렇게 중복된 결과가 나오면서, t=31일때 스코어는 240점 (40점을 6번더한것)이다.