[백준 21317번] 징검다리 건너기 (C++)

문제링크 : https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K, dp[21][2]; 
pii arr[21];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=1; i<N; i++)
    {
        int a, b;
        cin >> a >> b;
        arr[i] = {a, b};
    }
    cin >> K;

    for(int i=0; i<=N; i++)
    {
        dp[i][0] = MAX; 
        dp[i][1] = MAX; 
    }

    dp[1][0] = 0;
    dp[2][0] = arr[1].first; //두번째 돌

    for(int i=3; i<=N; i++)
    {
        dp[i][0] = min(arr[i-1].first + dp[i-1][0], arr[i-2].second+dp[i-2][0]); //작은 점프
        dp[i][1] = min({arr[i-1].first + dp[i-1][1], arr[i-2].second+dp[i-2][1], K+dp[i-3][0]}); //큰 점프 + 매우 큰 점프
    }

    cout << min(dp[N][0], dp[N][1]);

    return 0;
}

 

우선 매우 큰 점프 사용유무를 고려하여 dp 식을 세운다.

그리고 dp 식에서 최소값을 찾아야 하기에 우선 MAX 값으로 초기화를 진행해준다.

 

맨 처음에 해당하는 dp[1][0]은 시작점이기에 에너지 소모가 없으므로 0으로 초기화해주고,

두 번째에 해당하는 dp[2][0]은 케이스가 맨 처음에서 작은 점프하는 경우 밖에 없으므로 해당 값(작은 점프 값)으로 초기화해준다.

 

이제 반복문을 돌리며 i=3 ~ N까지 dp 식을 갱신하게 된다.

먼저 케이스를 살펴보면 다음과 같은 케이스가 존재한다.

작은 점프 -> 작은 점프
작은 점프 -> 큰 점프

큰 점프 -> 작은 점프
큰 점프 -> 큰 점프

0 1 차이는 매우 큰 점프 사용 유무 (1이 사용)

직전 작은 점프 : dp[i-1][0] or dp[i-1][1]
현재 작은 점프 : arr[i-1].first

직전 큰 점프 : dp[i-2][0] or dp[i-2][1]
현재 큰 점프 : arr[i-2].second

 

위 케이스에 대한 값들을 조합하여 dp 식을 갱신하게 된다.

 

이제 추가적으로 고려해야 하는 것은 큰 점프이다.

큰 점프의 경우 3칸을 점프하기에 반복문을 i=3부터 시작한 이유이기도 하다.

 

매우 큰 점프를 사용한 dp식을 갱신 할때 기존의 작은 점프, 큰 점프, 엄청 큰 점프 이렇게 3가지 값을 고려하게 된다.

현재 매우 큰 점프를 사용한 dp식이기 떄문에 작은 점프 및 큰 점프는 0이 아닌 1의 값을 가지게 된다.

하지만 매우 큰 점프의 경우 여태 사용하지 않고 이번에 사용하는 것이기 때문에 1이 아닌 0의 값을 가지게 된다.

(dp[i-3][0])

만약 dp[i-3][1] 이라면 이미 엄청 큰 점프를 사용했는데 또 사용하는 것을 의미하게 된다.

 

이후 엄청 큰 점프를 사용한 것과 아닌 것 중 (dp[N][0], dp[N][1]) 더 작은 값을 골라 출력해주면 된다.