오답노트 - 평범한 배낭

DP를 처음 접할 때의 기억들이 새록새록 떠올랐다. 이걸 어떻게 생각하지 싶었는데, DP에 나름 익숙해진 것 같아 뿌듯하다.

CODE

import sys
read=sys.stdin.readline

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

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

for w,v in things:
    for i in range(k-w,-1,-1):
        dp[i+w]=max(dp[i+w],dp[i]+v)

print(dp[-1])


숨바꼭질 2

어제 풀었던 탈출과 비슷한 종류의 DP 문제였다. 숨바꼭질 2는 수월하게 풀었지만, 숨바꼭질 3을 풀면서는 고민을 좀 했었다.

CODE

import sys
read=sys.stdin.readline

n,k=map(int,read().split())

from collections import deque

point=deque([n])
dp=list(-1 for _ in range(max(n,k)*2+1))
dp[n]=0

cnt,time=0,0

while point:
    for _ in range(len(point)):
        a=point.popleft()
        if a==k:
            time=dp[a]
            cnt+=1
        else:
            if a-1>=0 and (dp[a-1]==-1 or dp[a]+1==dp[a-1]):
                dp[a-1]=dp[a]+1
                point.append(a-1)
            if a+1<=k*2 and (dp[a+1]==-1 or dp[a]+1==dp[a+1]):
                dp[a+1]=dp[a]+1
                point.append(a+1)
            if a*2<=k*2 and (dp[a*2]==-1 or dp[a]+1==dp[a*2]):
                dp[a*2]=dp[a]+1
                point.append(a*2)
    if cnt!=0: break

print(time,cnt,sep='\n')


숨바꼭질 3

순간이동을 할 때, 100,000 이하의 점에 대해서는 모두 갈 수 있도록 했어야 했는데, 100,000 미만의 점에 대해 가도록 코드를 짜서 한동안 헤맸다.

CODE

import sys
read=sys.stdin.readline
from collections import deque
n,k=map(int,read().split())

len=100_000

point=deque([n])
dp=list(-1 for _ in range(len*2+1))
dp[n]=0

while point:
    a=point.popleft()
    if a==k:
        print(dp[a])
        break
    else:
        tmp=a
        while tmp<len*2 and tmp>=1:
            if dp[tmp]==-1:
                point.append(tmp)
                dp[tmp]=dp[a]
            tmp=tmp*2


        if a-1>=0 and dp[a-1]==-1:
            dp[a-1]=dp[a]+1
            point.append(a-1)
        if a+1<=len*2 and dp[a+1]==-1:
            dp[a+1]=dp[a]+1
            point.append(a+1)


풀어야 할 문제

  • 스타트 택시
  • 미네랄
  • 회전 초밥
  • 아기 상어
  • 전깃줄 -2
  • 치즈