[Silver 1] 21317 징검다리 건너기

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

21317번: 징검다리 건너기

 

이 문제는 DP를 사용해 해결할 수 있다.

 

문제를 보면 X 지점에서 돌을 건널 수 있는 경우의 수는 3가지이다.

X - 3

X - 2

X - 1

X

X+1

 

1. X-3 지점에서 엄청 큰 점프로 X로 이동

2. X-2 지점에서 큰 점프로 X로 이동

3. X-1 지점에서 작은 점프로 X로 이동

 

위 경우의 수가 일치하는 지점은 4번째 돌까지 이동했을 경우에 해당하기 때문에 이전의 이동 할 수 있는 경우의 수는 아래와 같다.

1. 작은 점프로 이동할 수 있는 경우

2. 큰 점프로 이동할 수 있는 경우

3. 작은 점프 2번으로 이동할 수 있는 경우

 

즉, DP[1]은 이동할 수 없으므로 0으로 초기화 한다. 또한 DP[1]은 작은 점프만 가능하다. 마지막으로 DP[2]는 작은 점프 2번과 큰 점프 중 작은 수로 초기화 한다.

 

문제에서 주의할 점은 엄청 큰 점프는 1번만 가능한 점이다. 

따라서 X지점에서 총 3가지 상태로 정의할 수 있다.

1. 이미 앞에서 큰 점프를 했을 경우

2. 돌 X에서 엄청 큰 점프를 할 경우

3. 돌 X에서 엄청 큰 점프를 하지 않을 경우

 

이를 다시 2가지 상태로 정의하면 돌 X 전후로 엄청 큰 점프를 사용했는지 안했는지로 나타낼 수 있다.

 

점화식으로 위에서 정의한 상태를 나타낸다면 DP[X][0], DP[X][1]로 나타낼 수 있다.

DP[X]는 지점을 나타낸다.

DP[X][0], DP[X][1]은 X지점에서 엄청 큰 점프의 사용 유무를 나타낸다.

1이면 돌 X이전에 이미 엄청 큰 점프를 사용한 것이고, 0이면 아직 사용하지 않은 것이다.

 

먼저 엄청 큰 점프를 사용하지 않았을 경우의 점화식은 아래와 같다.

DP[X][0] = MIN((X-1번째 돌의 작은 점프 에너지) + DP[X-1][0]),
((X-2번째 돌의 큰 점프 에너지) + DP[X-2][0])

 

점화식이 위 처럼 구해진 이유는 엄청 큰 점프를 제외한다면 X-1 과 X-2번째 돌에서 밖에 점프를 하지 못한다.

또한 엄청 큰 점프를 계속해서 하지 않을 것이기에 X-1과 X-2 번째 돌에서 점프 에너지를 누적하여 이중 최소 값을 저장하면 된다.

 

마지막으로 엄청 큰 점프를 사용했을 경우의 점화식이다.

DP[X][1] = MIN((X-1번째 돌의 작은 점프 에너지) + DP[X-1][1])
,((X-2번째 돌의 큰 점프 에너지) + DP[X-2][1]), K + DP[X-3][0])

 

점화식이 위처럼 구해진 이유는 엄청 큰 점프는 1번만 가능하다는 점이 있기 때문이다.

엄청 큰 점프를 사용하지 않았을 경우에 엄청 큰 점프의 에너지를 더하면 엄청 큰 점프를 1번만 사용할 수 있다.

또한 엄청 큰 점프를 사용한 이후에 작은 점프와 큰 점프와 엄청 큰 점프의 최소 값을 DP에 누적하면 된다.

 

N번째 돌까지 이동한 후 DP[N][0]과 DP[N][1] 중 최소 값을 출력하면 된다.

 

 

#include<iostream>
using namespace std;

int N, K;
pair<int,int> arr[21];
int dp[21][2];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    cin>>N;
    for(int i = 1;i<N;i++){
        cin>>arr[i].first>>arr[i].second;
    }
    cin>>K;
    for(int i = 0;i<=N;i++){
        dp[i][0] = 999999;
        dp[i][1] = 999999;
    }
    dp[1][0] = 0;
    dp[2][0] = arr[1].first;
    dp[3][0] = min(arr[1].first + arr[2].first,arr[1].second);
    for(int i =4;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(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])<<'\n';
    return 0;
}