문제
ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다.
여러 단원을 융합한 문제는 출제하지 않는다.
한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.
이런 두가지 힌트와 함께 각 단원 별 배점을 적어 놓으셨다. 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부하면 맞출 수 있다고 가정하자. 이때, ChAOS 회장 일로 인해 힘든 준석이를 위하여 남은 시간 동안 공부해서 얻을 수 있는 최대 점수를 구하는 프로그램을 만들어 주도록 하자.
풀이
문제를 보자마자 배낭문제와 유사하다고 생각했다.그래서 dp테이블의 정의를 해보면
dp[i][j] = i번째까지의 과목을 j시간동안 공부를 했을 때 최대 성적이라고 할 수 있겠다.
초기값 설정은 dp[0]이라면 과목이 없는 것이니까 0이어야 하고 dp[n][0]이라면 시간 투자를 안한 것이기 때문에 0으로 초기화 되어야 한다.
이 문제의 풀이에서는 처음부터 dp테이블을 0으로 초기화 하기 때문에 각 반복문을 1로 시작하면 된다.
dp[i-1][j]
dp[i-1]j-times[i-1]] + scores[i-1]
이 두 식을 비교해 최대값을 구하는 부분이 헷갈릴 수 있다고 생각한다.
기존 점수의 최대값(dp[i-1][j])과
추가될 점수와 현재 시간(current_time)에서 점수를 얻기 위한 시간값(times[i-1])을 뺀 곳의 최대값을 더한값을 비교한다고 생각하면 된다.(dp[i-1]j-times[i-1]] + scores[i-1])
N, K = map(int, input().split())
dp = [[0] * (K+1) for _ in range(N+1)]
times = []
scores = []
for _ in range(N):
time, score = map(int, input().split())
times.append(time)
scores.append(score)
for i in range(1, N+1):
for current_time in range(1, K+1):
if times[i-1] <= current_time:
dp[i][current_time] = max(dp[i-1][current_time], scores[i-1] + dp[i-1][current_time- times[i-1]])
else: dp[i][current_time] = dp[i-1][current_time]
print(dp[N][K])피드백
문제를 보고 바로 냅색문제라는 것을 알아낸게 그래도 큰 발전이라고 생각한다. dp문제를 계속 풀어나가는 건 좋은 선택인 것 같다. 유지하자.
