백준 15486 이진수 덧셈(파이썬)

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

풀이

모든 경우를 고려했을때 최댓값을 구하라는 것 문제의 요구사항에 따라서 DP문제임을 알 수 있다.

나는 특정일에 얻을 수 있는 최대 이익을 구하는데 집중을 하였다.

먼저 특정일에 주어진 일을 기간안에 완수할수 있는지 없는지를 확인하여야 한다.

그렇기에 특정 일에 주어진 일을 마무리 할 수 있는 날을 구한다. 

fin_date = idx + T[idx] - 1

이후 만약 마무리 할 수 있는 일의 마감 기한이 입력값 N보다 작다면 특정 일에 주어진 일을 완수해서 받을 수 있는 값과 특정 일을 하지 않았을때 받을수 있는 가격을 서로 비교한다.

dp[fin_date] = max(dp[fin_date], dp[idx-1] + P[idx])

그러나 이렇게만 코드를 작성한다면 마무리 할 수 있는 일의 마감 기한이 입력값 N보다 큰 값들에 대해서는 초기값을 업데이트 하지 못할것이다. 그렇기에 다음과 같은 코드를 추가하여 현재의 dp값과 전날의 dp값을 서로 비교해서 업데이트 해준다.

일종의 초기화 같은 역할을 한다.

dp[idx] = max(dp[idx], dp[idx-1])

코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
T, P = [0 for _ in range(N+1)], [0 for _ in range(N+1)]
dp =  [0 for _ in range(N+1)]

for idx in range(1, N+1):
    T[idx], P[idx] = map(int, input().split(" "))

for idx in range(1, N+1):
    dp[idx] = max(dp[idx], dp[idx-1])
    fin_date = idx + T[idx] - 1
    if fin_date <= N:
        dp[fin_date] = max(dp[fin_date], dp[idx-1] + P[idx])

print(max(dp))

배열의 끝부분을 다루는 코드와 range를 통해서 idx를 다루는 것이 미숙한 듯 하다.