[백준 14728번] 벼락치기

난이도: 골드 II

문제 링크: https://www.acmicpc.net/problem/14728

14728번: 벼락치기

 

이전에 풀었던 knapsack 문제와 완전히 동일합니다. (링크)

매우 자세한 설명은 위의 링크를 따라가면 있습니다.

오랜만에 다시 풀어본 김에 내용정리를 간단하게 하고 가자면...

 

이 문제는 모든 경우의 수를 고려하기에는 N <= 100, T <= 10000이고, N의 모든 경우의 수를 따진다면 시간 초과가 발생합니다.

이를 해결하기 위해 '같은 계산은 한 번만 하는' dp를 이용하여 해결할 수 있습니다.

 

N * T 크기의 table dp를 만듭니다. dp의 내부에는 해당 시점까지 얻은 성적이 기록되며, dp[N][T]에는 주어진 조건에 맞는 최고의 성적이 나옵니다.

N(i)은 각 단원을 의미하며, T(j)는 총 가능 공부 시간입니다. 따라서 각 물건을 들고 시작했을때를 기준으로, 물건을 집을 때 가치가 더 큰 곳을 고르는 과정입니다.

 

j가 현재 과목의 공부시간보다 작다면, dp[i][j] = dp[i-1][j].

j가 현재 과목의 공부시간과 크거나 같다면, dp[i][j] = max(dp[i-1][j], dp[i-1][j-공부시간] + 얻을 수 있는 성적) 이 됩니다.

 

코드로 구현하면 아래와 같습니다.

 

 

채점 결과

 

오랜만에 문제를 접했더니 점화식이 가물가물 했네요 ㅎㅎ;