[백준(BOJ)] #14728- 벼락치기 (파이썬, PyPy3)

문제

 

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

14728번: 벼락치기

---

문제 풀이

2022.08.12 - [PS/백준] - [백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3)

[백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3)

전형적인 배낭 문제로 저번에 올렸던 문제 평범한 배낭과 같은 유형의 문제입니다. 마찬가지로 동적 계획법을 사용해 해결할 수 있습니다. 자세한 설명은 위에 올린 평범한 배낭 문제 풀이를 보면 될 것 같네요!

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, t = map(int, input().split())
    dp = [0] * (t+1)
    
    for _ in range(n):
        k, s = map(int, input().split())
        for i in range(t, -1, -1):
            if i >= k:
                dp[i] = max(dp[i], dp[i-k] + s)
    print(dp[t])

결과