[백준] 15846. 퇴사 2 - Python

[Gold V]

 

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

15486번: 퇴사 2

 

풀이 1

문제를 보니, Greedy는 아닌 것 같고.. DP로 접근해야겠다는 생각으로 문제를 읽기 시작.

첫 시도에는, 1차원 dp이고, 1일차 부터 Bottom-Up으로 채워나가는 식으로 접근하려고 시도했다.

 

예제 입력 1 은 아래와 같다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

 

이런 상황에서, 1일차부터 접근하면 되겠다는 생각이였음.

당연하게도, dp[i] 테이블을, dp[i] = (i+1)일차까지 받을 수 있는 금액의 최댓값. 으로 잡고 시작했다.

dp[i + T[i]] = max(dp[i] + P[i], dp[i + T[i]]) 와 같이 점화식을 잡고 계산하면 될 것이라 생각했는데, WA.

N = int(input())

T = []
P = []
for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)
    
# dp[i] = (i+1)일차부터 받을 수 있는 금액의 최댓값.
dp = [0]*(N+1)

for i in range(N):
    if i + T[i] > N:
        continue
    
    dp[i + T[i]] = max(dp[i] + P[i], dp[i + T[i]])

print(dp)

 

 

풀이 2

요 라인 하나를 빠뜨렸다.

(i+1)일 째를 계산할 때, (i)일 째의 최댓값과 (i+1)일 째의 최댓값 (dp[i-1]과 dp[i])를 미리 비교하여 dp[i]에 대입해야,

(i)일 째에 아무 일도 하지 않았을 때의 최댓값을 그대로 전해줄 수 있다.

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

 

AC.

N = int(input())

T = []
P = []
for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)
    
# dp[i] = (i+1)일차부터 받을 수 있는 금액의 최댓값.
dp = [0]*(N+1)

for i in range(N):
    dp[i] = max(dp[i], dp[i-1])
    if i + T[i] > N:
        continue
    
    dp[i + T[i]] = max(dp[i] + P[i], dp[i + T[i]])

print(dp)