문제 바로가기
문제:
심마니 영재는 산삼을 찾아다닌다. 산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다. 마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다. 점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다. 각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다. 매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다. 에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라. 영재는 첫 번째 돌에서부터 출발한다.
입력:
첫 번째 줄에는 돌의 개수 N이 주어진다. N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다. 마지막 줄에는 K가 주어진다.
출력:
산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.
풀이:
import copy
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N = int(input())
dp =[0] + [1e9] * (N-1)
jump = []
# 슈퍼점프 아직 미사용
for i in range(N-1):
x, y = map(int,input().split())
jump.append((x, y))
# 원점
if i+1 < N:
dp[i+1] = min(dp[i] + x,dp[i+1])
# 투쩜
if i+2 < N:
dp[i+2] = min(dp[i] +y , dp[i+2])
res=dp[-1]
k = int(input())
for idx in range(0, N-3):
new_dp=copy.deepcopy(dp)
if dp[idx] + k < dp[idx+3]:
new_dp[idx+3] = dp[idx]+k
for j in range(idx+4, N):
new_dp[j] = min(dp[j], new_dp[j-1]+jump[j-1][0], new_dp[j-2]+jump[j-2][1])
res = min(res,new_dp[-1])
print(res)
굉장히 어려운 문제였다. 입력값 이해 하는데도 시간이 걸렸다.
jump 에 들어가는 값은 작은 점프하는데 드는 비용과, 큰 점프를 하는데 드는 비용이다.
처음 0에서 1로 점프할때 는 앞에 입력값이고
2로에 점프는 1>2 와 0 > 2 가 되기때문에 왼쪽 입력값이 작은 점프, 오른쪽 입력값이 큰 점프가 된다.
N = int(input())
dp =[0] + [1e9] * (N-1)
jump = []
# 슈퍼점프 아직 미사용
for i in range(N-1):
x, y = map(int,input().split())
jump.append((x, y))
# 원점
if i+1 < N:
dp[i+1] = min(dp[i] + x,dp[i+1])
# 투쩜
if i+2 < N:
dp[i+2] = min(dp[i] +y , dp[i+2])
res=dp[-1]
처음 슈퍼 점프 하기 이전에 dp를 만들어둔다.
- i+1 < N
- 원 점프가 가능한 경우다. 다음 점프할 곳은 현재 돌 + 다음 돌까지 작은점프비용, 중에 최솟값으로 최신화 시키면 된다.
- i+2 < N
- 두 점프가 가능한 경우. 2개 이전 돌 + 큰 점프, 현재 위치 점수
dp 이후에 res에 마지막 돌의 최솟 값을 저장한다.
k = int(input())
for idx in range(0, N-3):
new_dp=copy.deepcopy(dp)
if dp[idx] + k < dp[idx+3]:
new_dp[idx+3] = dp[idx]+k
for j in range(idx+4, N):
new_dp[j] = min(dp[j], new_dp[j-1]+jump[j-1][0], new_dp[j-2]+jump[j-2][1])
res = min(res,new_dp[-1])
print(res)슈퍼점프를 이제 1번만 사용하여 dp 를 바꾼다. 슈퍼점프를 한 번만 사용하는것은, 슈퍼 점프가 가능한 0부터 N-3 한번씩 사용한 것을 확인해본다. 만약 N-3을 넘어가서 슈퍼점프하면 마지막 돌을 넘어가 버린다.
deepcopy는 기존 배열의 입력값을 유지한다. 새로운 dp를 똑같이 만든다. 서로 영향은 받지 않는다.
만약 기존의 어떤 돌에 가는 값이, 현재 돌에서 슈퍼 점프 했을때 값이 더 크면, 그 이후의 dp를 최신화 시켜준다.
ex) dp[6] = 10 이고 dp[3] = 3, k =3 이면 3에서 슈퍼점프하면 6으로 값이 더 작아, 6으로 최신화 시켜주는 것이다.
그러면 dp[6] 을 최신화시켜 주고 그 다음 idx부터 N까지 확인 해주면 된다.
for j in range(idx+4, N):
new_dp[j] = min(dp[j], new_dp[j-1]+jump[j-1][0], new_dp[j-2]+jump[j-2][1])그 부분을 식으로 나타내면 다음과 같다.
기존의 dp[j], 한개 전 돌에서 작은점프 new_dp[j-1] + jump[j-1][0], 2개 전 돌에서 큰 점프 new_dp[j-2] + jump[j-2][1] 을 해준다.
그리고 최솟값 갱신 후 답 출력
댓글