[Python] 21317번 징검다리 건너기

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

21317번: 징검다리 건너기

---

 

22/10/03

 

 

개인적으로 굉장히 난이도에 비해 굉장히 어렵게 느껴졌던 문제로, 다른 방법으로 풀었다면 조금 쉽게 해결하지 않았을까 하는 아쉬움이 남는 문제이기도 하다.

---

 

문제 접근 방식:

 

 

백트래킹으로도 접근할 수 있는 문제이긴 하지만, 나의 경우는 DP로 이 문제를 접근했었다.

 

굉장히 많이 틀렸기 때문에 틀린 과정을 상세하게 설명하고자 한다.

 

맨 처음 풀이는 그냥 단순하게 DP[N] = N번째까지 도착했을 때, 산삼을 얻기 위해 필요한 영재의 에너지 최솟값이라고 정의를 했었다.

 

그리고 가장 큰 점프는 한 번만 할 수 있으므로, 가장 큰 점프를 했는지 안 했는지의 여부를 1과 0으로 구분하여 DP점화식에 튜플로 저장하는 방식을 택했다.

 

DP[i]를 구할 때에는 이전 것을 참조하여 구했는데, 이전 것들이 가장 큰 점프를 했다면 안 하는 쪽으로, 안 했다면 하는 행동도 고려하여 min값을 구하는 방식으로 DP table을 채워나갔다.

 

이와 비슷한 방식으로 여러 번 했는데, 모두 틀렸다.

 

그 이유는 위 방식처럼 DP점화식을 정의한다면, 가장 큰 점프를 나중에 하는 것이 이득인 상황이 있을 수도 있는데, 그 이전에 가장 큰 점프를 미리 써버려서 잘못된 결과가 나올 수도 있기 때문이다.

 

나는 코드를 여러 번 다듬은 결과, 가장 큰 점프는 한 번만 사용할 수 있다는 사실에 근거하여, DP배열을 2가지로 분리하였다.

 

첫 번째 DP배열은 가장 큰 점프를 하나도 사용하지 않고, 그냥 단순히 N번째까지 도착했을 때, 산삼을 얻기 위해 필요한 영재의 에너지 최솟값을 저장하는 배열이다.

 

때문에 DP1[i] = min(DP1[i-2] + (i-2)번째 칸에서 큰 점프하는 에너지 양, DP1[i-1] + (i-1)번째 칸에서 작은 점프하는 에너지 양)이 나온다.

 

이후, DP2배열을 만들어주는데, 이는 가장 큰 점프를 사용했을 때 그 에너지의 최솟값을 저장하는 배열이다.

 

나는 가장 큰 점프를 첫번째 칸에 쓰냐, 두 번째 칸에 쓰냐, 세 번째 칸에 쓰냐, 더 나아가서 (N-3) 번째 칸에 쓰냐에 따라서 DP2[N]의 최종 값이 달라짐을 시행착오를 통해 알게 되었기 때문에, 다음과 같은 방식으로 구현했다.

 

DP2 배열은 기본적으로 DP1배열을 그대로 복사한 배열인데, k번째 돌에서 가장 큰 점프를 했다는 것만 다르다.

 

그러면 DP2[k+3] = DP1[k] + (가장 큰 점프를 할 때에 드는 에너지 양)이 되는데, DP2[k+4]부터는 DP1배열을 구성했던 것처럼 점화식을 그대로 사용하면 된다. (DP2[i] = min(DP2[i-2] + (i-2) 번째 칸에서 큰 점프하는 에너지 양, DP2[i-1] + (i-1) 번째 칸에서 작은 점프하는 에너지 양))

 

최종적으로 DP2[N]의 값이 나올 텐데, 이 값은 위에서 언급했듯, 몇 번째 돌에서 가장 큰 점프를 했냐에 따라서 달라진다.

 

때문에 이 DP2[N]의 값들을 구할 때에는 for문을 사용하여 가능한 모든 DP2[N]값들을 구해주고, 이를 energy_list라는 리스트에 모두 저장하여 그 energy_list의 최솟값을 출력하는 방식으로 구현하였다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21317번 징검다리 건너기
# DP
'''
접근 방법:
DP1[N] = N번째까지 도착했을 때, 매우 큰 점프 없이 산삼을 얻기 위해 필요한 에너지 최솟값
DP2 -> [] 계속 append
1번째돌에서 슈퍼점프한 후 ~~
두번째 돌에서 슈퍼점프 한 후 ~~
세번째 돌에서 슈퍼점프 한 후 ~~
k번째 돌에서 슈퍼점프 한다면
DP2 = DP1.copy
DP2[k+3] = DP1[k] + very_big_jump
DP2를 DP1만든것처럼 계속 갱신해줘(k+4)부터
DP2[N]
~~N-3번째 돌에서 슈퍼점프 한 후~~
'''
from copy import deepcopy

N = int(input())
small_jump = []
big_jump = []

for _ in range(N-1):
    small, big = map(int, input().split())
    small_jump.append(small)
    big_jump.append(big)
very_big_jump = int(input())

if N >= 3: # 일반적인 케이스
    DP1 = [0 for _ in range(N)]
    DP1[0] = 0
    DP1[1] = small_jump[0]
    for i in range(2, N):
        DP1[i] = min(DP1[i-2] + big_jump[i-2], DP1[i-1] + small_jump[i-1])
    energy_list = [DP1[N-1]]
    for k in range(N-3):
        DP2 = deepcopy(DP1)
        DP2[k+3] = DP1[k] + very_big_jump  # k번째 돌에서 슈퍼점프
        for i in range(k+4, N):
            DP2[i] = min(DP2[i-2] + big_jump[i-2], DP2[i-1] + small_jump[i-1])
        energy_list.append(DP2[N-1])
    print(min(energy_list))
elif N == 3:
    print(min(sum(small_jump), big_jump[0]))
elif N == 2:
    print(small_jump[0])
else:
    print(0)