[BOJ] 징검다리 건너기 21317 C++

 

 

문제

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

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

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

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

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

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

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

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

입력

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

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

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

출력

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

 

접근 방식

 

작은점프, 큰점프, 매우 큰 점프 중 가장 최솟값을 저장해 나가는 DP문제이다

근데 이때 매우 큰 점프는 1번만 가능하기 때문에

DP를 2차원 배열로 두어야 한다!

 

근데 자꾸 맞왜틀 이길래

조금 해맸던 문제..

 

1번이라는 거에 자꾸 빠져서 점프 한 이후에 처리를 잘해주어야 한다는 것을 놓쳤었다

코드는 매우 간단한데 DP 문제 풀 때 이런부분 유의해서 풀어야 겠다고 생각!

 

소스 코드

 

#include<bits/stdc++.h>
using namespace std;

int N,K;
vector<pair<int,int>> v;
int dp[25][2];

int main() {
    cin>>N;
    v.push_back({0,0});
    for(int i=0; i<N-1; i++) {
        int s,m; cin>>s>>m;
        v.push_back({s,m});
    }
    cin>>K;

    memset(dp, 0x7f7f7f, sizeof(dp));

    dp[1][0] =  0;
    dp[2][0] = v[1].first;
    dp[3][0] = min(dp[2][0] + v[2].first, dp[1][0] + v[1].second);

    for(int i=4; i<=N; i++) {
        dp[i][0] = min(dp[i-1][0] + v[i-1].first, dp[i-2][0] + v[i-2].second);

        dp[i][1] = min({v[i-1].first+dp[i-1][1], v[i-2].second+dp[i-2][1], K+dp[i-3][0]});
    }


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


}