평범한 배낭


평범한 배낭 포스팅에서 2주전에 다뤘던 똑같은 문제다. 포스팅 할때 굉장히 애를 먹었던걸로 기억하는데 한번에 잘 풀려서 뿌듯하다. 비교적 쉬운 문제지만, 확실히 조금씩은 늘고 있다는 느낌을 받을 수 있었다.


CODE

import sys
read=sys.stdin.readline

n,k=map(int,read().split())
thing=list(list(map(int,read().split())) for _ in range(n))

dp=list(0 for _ in range(k+1))

for i in range(n):
    weight=thing[i][0]
    value=thing[i][1]
    for j in range(k-weight,-1,-1):
        dp[j+weight]=max(dp[j+weight],dp[j]+value)

print(max(dp))



트리 가짓수 세기

규칙을 찾아보고, 이진 검색 트리의 깊이도 찾아봤는데, 해결할 기미가 안보인다… 일요일 전까지 풀어보자.

2020.10.18 못풀었습니다…



CODE