[파이썬] 백준 15486 : 퇴사2 (골드5)

[파이썬] 백준 15486 : 퇴사2 (골드5)

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

---

풀이

방향성 생각

• N이 150만이라 바텀업으로 $O(N)$으로 푸는게 합리적으로 보인다.

---

전체코드

# Solution 1
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
arr = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0]*(N+1)

for t in range(N):
    Tt,Pt = arr[t]
    nt = t+Tt
    if nt <= N:
        dp[nt] = max(dp[nt],dp[t]+Pt)
    dp[t+1] = max(dp[t+1],dp[t]) 
print(dp[N])

# Solution 2
import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [-1]*N

def dfs(x):

    if x == N:
        return 0

    if dp[x] != -1:
        return dp[x]

    result = dfs(x+1)
    Tx,Px = arr[x]
    if x + Tx <= N:
        result = max(result,Px+dfs(x+Tx))

    dp[x] = result
    return dp[x]

print(dfs(0))

코멘트

• Solution 1: 바텀업
  • dp size를 N으로 할거면 정산 날짜를 t+Tt-1로 잡아서 강연이 마무리 되는 날에 업데이트 한다.
  • 그렇지 않고 더미 인덱스 만들어서 풀이도 가능함.
  • 식 자체는 어렵지 않게 기간 내로 끝낼 수 있는 경우 t에서 nt로 이동하면서 Pt 더해주기.
  • 또는 강연을 하지 않는 경우는 이전 날짜 값과 저장 값중 최대값 풀이
• Solution 2: 탑다운
  • 파이썬 절망편 : python3 TLE + pypy3 MLE