[백준] 21317 징검다리 건너기

📖 문제

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

💻 내 코드

n=int(input())
mlist=[[0]*2 for _ in range(n-1)]
for i in range(n-1):
    a, b=map(int,input().split())

    mlist[i][0]=a
    mlist[i][1]=b

k=int(input())

if n==1:
    print(0)
    exit()
elif n==2:
    print(mlist[0][0])
    exit()
dp=[0]*n

dp[1]=mlist[0][0]
dp[2]=min(mlist[0][0]+mlist[1][0], mlist[0][1])
for i in range(3, n):
    dp[i]=min(mlist[i-1][0]+dp[i-1], mlist[i-2][1]+dp[i-2])

res=dp[-1]
dp2=dp[:]

for i in range(0, n-3):
    if dp[i]+k<dp[i+3]:
        dp2[i+3]=dp[i]+k
        for j in range(i+4, n):
            dp2[j]=min(dp[j], dp2[j-1]+mlist[j-1][0], dp2[j-2]+mlist[j-2][1])
        if dp2[-1]<res:
            res=dp2[-1]
print(res)

💡 풀이

dp[1]=mlist[0][0]
dp[2]=min(mlist[0][0]+mlist[1][0], mlist[0][1])
for i in range(3, n):
    dp[i]=min(mlist[i-1][0]+dp[i-1], mlist[i-2][1]+dp[i-2]) 

• 1번 돌을 갈 수 있는 방법: 작은 점프만 가능
• 2번 돌을 갈 수 있는 방법: 1번으로 작은 점프+2번으로 작은 점프 또는 2번으로 큰 점프 중 작은 값
• 3번~마지막 돌을 갈 수 있는 방법: 전전 돌을 가는 벙법+전 돌에서 작은 점프, 전전전 돌을 가는 방법+전전 돌에서 점프 중 작은 값

res=dp[-1]

for i in range(0, n-3):
	dp2=dp[:]
	
    if dp[i]+k<dp[i+3]:
        dp2[i+3]=dp[i]+k
        for j in range(i+4, n):
            dp2[j]=min(dp[j], dp2[j-1]+mlist[j-1][0], dp2[j-2]+mlist[j-2][1])
        if dp2[-1]<res:
            res=dp2[-1]

• dp2: 새로운 값을 계산 하기 위한 dp의 복사본
• 만약 dp[i]+k의 값이 i에서 매우 큰 점프를 한 곳의 원래의 값인 dp[i+3]보다 작아면 그 곳부터 새로 dp를 계산해준다
• 가능한 방법은 원래 값과 위와 같은 방법으로 구할 수 있는 값 중 작은 값
• 원래 결과와 비교하여 더 작은 값이 정답