징검다리 건너기

문제

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

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

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

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

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

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

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

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

입력

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

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

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

출력

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

제한

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

예제 입력 1

예제 출력 1 복사

풀이

먼저 문제를 이해해보자.

영재가 N개의 돌을 건너는데 필요한 최소 에너지를 구해야 한다.
돌을 건너는데 점프의 종류는 총 3가지이다.
1. 작은 점프: 1개의 돌 건너뛰기
2. 큰 점프: 2개의 돌 건너뛰기
3. 매우 큰 점프: 3개의 돌 건너뛰기 (딱 한번만 가능)

설계

5
1 2
2 3
4 5
6 7
4

예제를 확인해보자.

N = 5
1번 돌: 작은 점프 에너지 1, 큰 점프 에너지 값 2
2번 돌: 작은 점프 에너지 2, 큰 점프 에너지 3
3번 돌: 작은 점프 에너지 4, 큰 점프 에너지 5
4번 돌: 작은 점프 에너지 6, 큰 점프 에너지 7
K = 4

나는 dp의 bottom-up 방식을 사용하여 이 문제를 해결하였다.

각 점프는 3개이고, N번째 돌에 도달할 때까지 점프의 에너지를 합하여 최종적으로 최소 에너지를 구하면 된다.

dp 테이블은 두 개로 나누었다.

1. dp [ i ] [ 0 ]

: i번째 돌에 도착할 때, 매우 큰 점프를 사용하지 않았을 때 사용한 최소 에너지.

작은 점프와 큰 점프 마음대로 사용 가능

2. dp [ i ] [ 1 ]

: i번째 돌에 도착할 때, 매우 큰 점프를 단 한번 사용했을 때 사용한 최소 에너지.

이전에 매우 큰 점프를 한 경우: 작은 점프와 큰 점프 마음대로 사용 가능
매우 큰 점프를 하지 않은 경우: 모든 점프 가능

구현

위의 설계를 바탕으로 점화식을 만들어보자.

1. 매우 큰 점프가 없는 경우

매우 큰 점프가 없으니 작은 점프와 큰 점프만 고려해준다.

dp[i+1][j] = min(dp[i+1][j], dp[i][j] + small)
dp[i+2][j] = min(dp[i+2][j], dp[i][j] + big)

dp[i][j] + small = i+1번째 돌에서 작은 점프
dp[i][j] + big = i+2번째 돌에서 큰 점프

2. 매우 큰 점프가 있는 경우

dp[i+3][1] = min(dp[i+3][1], dp[i][0] + K)

dp[i][0] + k = i 번째 돌에서 매우 큰 점프를 하는 경우

=> 최종적으로 dp [ N ] [ 0 ] , dp [ N ] [ 1 ] 중 작은 값을 출력한다.

전체 코드

let N = Int(readLine()!)!

var arr : [[Int]] = Array(repeating: Array(repeating: 0, count: 2 ), count: N)
var dp : [[Int]] = Array(repeating: Array(repeating: Int.max, count: 2), count: N+4)

dp[1][0] = 0
dp[1][1] = 0

for i in 1..<N {
    let Input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i][0] = Input[0]
    arr[i][1] = Input[1]
}

let K = Int(readLine()!)!

for i in 1..<N {
    let small = arr[i][0]
    let big = arr[i][1]
    
    for j in 0..<2 {
        dp[i+1][j] = min(dp[i+1][j], dp[i][j] + small)
        dp[i+2][j] = min(dp[i+2][j], dp[i][j] + big)
    }
    
    dp[i+3][1] = min(dp[i+3][1], dp[i][0] + K)
}

print(dp[N].min()!)