[BOJ 21317 🥈1] 징검다리 건너기 (Python)

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

21317번: 징검다리 건너기

문제

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

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

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

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

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

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

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

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

입력

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

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

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

출력

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

제한

• 1 ≤ N ≤ 20
• 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.

예제 입력 1

5
1 2
2 3
4 5
6 7
4

예제 출력 1

5

 

⭕ CODE

# 돌의 개수
n = int(input())

# 점프들을 담기 위한 리스트 arr
arr = [[0, 0]]
for _ in range(n - 1):
    small, big = map(int, input().split())
    arr.append([small, big])

# 큰 점프
k = int(input())

d = [0] * (n + 1)

d[0] = 0
# 돌이 한개라면
if n == 1:
    # 점프가 필요 없으므로 0 출력
    print(0)
# 돌이 2개라면
elif n == 2:
    # 1번으로 가는 작은점프 arr[1][0]출력
    print(arr[1][0])
# 돌이 3개 이상이라면
else:
    # 1까지의 최소는 1로가는 작은 점프
    d[1] = arr[1][0]
    # 2로가는 최소는
    # 1로가는 최소에서 2로가는 작은점프 d[1]+arr[2][0]
    # 바로 2로가는 큰점프 arr[1][1]
    # 2개 중 최소값
    d[2] = min(d[1] + arr[2][0], arr[1][1])

    for i in range(3, n):
        # i로 가는 최소는
        # i-1에서 작은점프로 다음돌로 이동하는 d[i-1] + arr[i][0]
        # i-2에서 큰 점프로 1개의 돌을 건너뛰어 이동하는 d[i-2] + arr[i-1][1]
        d[i] = min(d[i - 1] + arr[i][0], d[i - 2] + arr[i-1][1])
	
    # 매우 큰 점프를 사용하지 않고 n-1번째 돌로가는 최소의 에너지
    result = d[n-1]

    # 매우 큰 점프는 2칸을 건너뛰므로 3번부터 시작
    for i in range(3,n):
    	# 새로운 dp 배열 생성
        dp = d[:]
        # i번째 돌로 매우 큰 점프 하기
        dp[i] = d[i-3] + k
        
        # i+1번째 돌부터 위와 동일하게 최소를 구하기
        for j in range(i+1,n):
            dp[j] = min(dp[j - 1] + arr[j][0], dp[j - 2] + arr[j-1][1])
		
        # 매우 큰 점프를 사용한것이 더 작다면
        # result값 변환
        if result > dp[n-1]:
            result = dp[n-1]
    print(result)

✏️ Comment

시간이 엄청 많이 걸렸던 문제이다. 처음에는 매우 큰 점프를 한 번만 사용한다는 조건을 깜빡하고 다 사용해서 틀렸다. 이거를 다시 확인하고 매우 큰 점프를 한 번도 안한 d배열을 구하고 매우 큰 점프를 하는 모든 경우에 대해서 최소값을 비교하였다.

최솟값 비교 과정에서도 처음에는 result 값을 매우 큰 값을 설정하였는데 매우 큰 점프를 한 번도 안한 경우가 최솟값이 될 수 있다고 생각하여 result의 초기 값을 d[n-1]로 지정하였다.

가장 시간이 오래 걸렸던 부분은 2로 가는 최소를

d[2] = min(d[1] + arr[2][0], arr[2][1])​
#d[2] = min(1 + 2, 3)

로 생각했다. 

5
1 2
2 3
4 5
6 7
4​

 

이 경우에서 2로 가는 경우를 1에서 2로가는 1+2와 바로 2로가는 3으로 생각했는데
문제에서 요구한 내용은 2로 바로가는 2였던 것이다. 그래서 위의 코드를 

d[2] = min(d[1] + arr[2][0], arr[1][1])​
#d[2] = min(1+2,2)

이런 형태로 모두 바꾸어 주었더니 바로 통과했다.

돌이 1개인 경우와 2개인 경우도 생각해 주어야 했다. 처음에 1인 경우는 잘 처리했지만 2의 경우를 처리하지 않아서 index 에러가 발생했다. 만약 코딩 테스트였다면 여기서 걸렸을 것이다. 모든 예외 처리를 시도해 보자

 

• 문제를 꼼꼼하게 잘 읽고 이해를 똑띠하자!!!