[파이썬] 백준 14728 : 벼락치기 (골드5)

[파이썬] 백준 14728 : 벼락치기 (골드5)

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

---

풀이

방향성 생각

• 냅색 기본문제
• 상한선이 주어진 무언가가 있을 때 최댓값을 찾는 문제

---

전체코드

N,T = map(int,input().split())

dp = [[0]*(T+1) for _ in range(N+1)] # T시간 썼을 때 얻을 수 있는 점수 최대값
for i in range(1,N+1):
    t,s = map(int,input().split())
    for j in range(T+1):
        if j >= t:
            # max(현재 문제를 풀지 않는 경우 / 현재 문제를 푼 경우)
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-t]+s)
        else:
            # 문제를 풀지 못하는 경우
            dp[i][j] = dp[i-1][j]
print(max(dp[-1]))

코멘트

• 각 상태를 node로 표현해서 바텀업으로 표현하면 쉽게 풀 수 있다.
• 질문 게시판에도 나와있지만, 문제를 풀지 못하는 경우에도 업데이트를 해줘야한다.