21317(징검다리 건너기) - 해결

징검다리 건너기 

 

문제

심마니 영재는 산삼을 찾아다닌다.

산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.

마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.

점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.

각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.

매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.

에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.

영재는 첫 번째 돌에서부터 출발한다.

 

입력

첫 번째 줄에는 돌의 개수 N이 주어진다.

N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.

마지막 줄에는 K가 주어진다.

 

출력

산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.

---

제대로 한거 같은데 왜 안될까?

dp로 풀었는데 왜지? 테스트도 다 맞는데

import sys

N = int(sys.stdin.readline())

energys = [[0,0]]
for _ in range(1,N):
    energys.append(list(map(int,sys.stdin.readline().split())))

def Kindex():
    k = [0] * (N-2)
    for i in range(1,N-2):
        k[i] = min(energys[i][0]+energys[i+1][0]+energys[i+2][0],energys[i][1]+energys[i+2][0],energys[i][0]+energys[i+1][1])
    if max(k) > K:
        return k.index(max(k))
    else:
        return 0

K = int(sys.stdin.readline())
dp = [5000*N] + [0] + [5000*N] * (N+1)

i = 1
while i < N:
    print(dp)
    print(Kindex())
    if i == Kindex():
        dp[i+3] = dp[i] + K
        i += 3
        continue

    dp[i+1] = min(dp[i+1],dp[i]+energys[i][0])
    dp[i+2] = min(dp[i+2],dp[i]+energys[i][1])
    i += 1
    
    # K를 해결해야한다. 
    # 어디서에 쓰는게 가장 효율적인지 찾아야함.
    #dp[i+3] = min(dp[i+3],dp[i]+K)
print(dp[N])

안되는 이유는 kindex를 찾는 과정에서 같은 에너지를 소모하는 곳이 겹쳐있다면 비교를 하는 과정이 필요하다.

이 과정을 브루트포스로 모든 가능한 k 점프를 하고 가장 작은 값을 저장하였다.

그러나 95퍼에서 틀리기에 여러가지 찾아 보던중 3보다 작을때를 생각을 안했다. 그래서 그 부분도 추가하였다.

히든 케이스가 역시나 너무 어렵다... 생각을 넓게하자

import sys

N = int(sys.stdin.readline())

# 작은 점프와 큰점프를 저장
energys = [[0,0]]
for _ in range(1,N):
    energys.append(list(map(int,sys.stdin.readline().split())))

# 매우 큰 점프
K = int(sys.stdin.readline())
# dp는 1번 돌은 0이라고 저장을 해야 비교가 가능.
# 그리고 0번 돌과 N+1,N+2 돌도 인덱스를 위해 추가
dp = [5000*N + 1] + [0] + [5000*N + 1] * (N+1)

# 모든 과정을 다보고 가장 작은 값을 저장하기 위해
minN = 5000*N + 1

# 돌이 1개일때
if N == 1:
    print(0)
# 2개일 때
elif N ==2:
    print(energys[1][0])
# 3개 이상.
else:
    # 매우 큰 점프를 안하는거 부터 1~N-3번 돌까지 해보기
    for k in range(N-2):
        #초기화
        dp = [5000*N + 1] + [0] + [5000*N + 1] * (N+1)
        i = 1
        # 이제 순회
        while i < N:
            # 매우 큰 점프를 할 돌    
            if i == k:
                dp[i+3] = dp[i] + K
                i += 3
                continue
            # 다음돌과 다다음 돌은 이 중에서 작은 걸 넣는다.
            dp[i+1] = min(dp[i+1],dp[i]+energys[i][0])
            dp[i+2] = min(dp[i+2],dp[i]+energys[i][1])
            # 다음 돌
            i += 1
        # 매번 N 번째 돌까지 도착하는 에너지와 비교
        minN = min(minN,dp[N])
    print(minN)