반응형
작은 점프, 큰 점프 그리고 단 한번의 매우 큰 점프를 통해 마지막 돌로 가는 최소 에너지를 구하는 문제.
우선 단 한번의 매우 큰 점프를 제외하고 생각했다. 단 한번은 예외처리를 해주면 되니까 라는 생각에서 그랬다.
n까지 가는데 드는 최소 에너지 dp(n)은 dp(n-1)+작은점프, dp(n-2)+큰점프 중 큰 값이다.
코드로 구현하면
n=int(input())
d=[[0,0]]
for _ in range(n-1):
d.append(list(map(int,input().split())))
dp=[0 for x in range(n+1)]
if n==1:
print(0)
exit()
elif n==2:
print(d[1][0])
exit()
dp[2]=d[1][0]
dp[3]=min(d[1][0]+d[2][0],d[1][1])
for x in range(4,n+1):
dp[x]=min(dp[x-1]+d[x-1][0],dp[x-2]+d[x-2][1])n=1, n=2일때는 예외 상황이므로 제외처리 해주었다.
여기까지가 큰 점프와 작은 점프로 마지막 돌에 가는 방법이다.
그 뒤는 매우 큰 점프를 적용시키는 것인데, 단 한번이므로 모든 돌에서 점프하는 경우를 따져서 구현했다.
k=int(input())
MIN=9999999
for x in range(1,n-2):
dpcopy=dp[:]
if dp[x]+k<dp[x+3]:
dpcopy[x+3]=dpcopy[x]+k
for t in range(x+4,n+1):
dpcopy[t]=min(dpcopy[t],dpcopy[t-1]+d[t-1][0],dpcopy[t-2]+d[t-2][1])
if MIN>dpcopy[-1]:
MIN=dpcopy[-1]dp리스트를 그대로 사용하게되면 이후 반복문에서 영향을 미치므로 dpcopy라는 새로운 리스트를 만들어서 사용했다. 그리고 최소값보다 작으면 최소값을 dpcopy[-1]로 갱신한다.
따라서 전체코드는 다음과 같다.
n=int(input())
d=[[0,0]]
for _ in range(n-1):
d.append(list(map(int,input().split())))
dp=[0 for x in range(n+1)]
if n==1:
print(0)
exit()
elif n==2:
print(d[1][0])
exit()
dp[2]=d[1][0]
dp[3]=min(d[1][0]+d[2][0],d[1][1])
for x in range(4,n+1):
dp[x]=min(dp[x-1]+d[x-1][0],dp[x-2]+d[x-2][1])
k=int(input())
MIN=9999999
for x in range(1,n-2):
dpcopy=dp[:]
if dp[x]+k<dp[x+3]:
dpcopy[x+3]=dpcopy[x]+k
for t in range(x+4,n+1):
dpcopy[t]=min(dpcopy[t],dpcopy[t-1]+d[t-1][0],dpcopy[t-2]+d[t-2][1])
if MIN>dpcopy[-1]:
MIN=dpcopy[-1]
if MIN==9999999:
print(dp[-1])
else:
print(MIN)반응형
