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

21317번 :징검다리 건너기

---

문제)

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

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

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

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

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

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

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

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

 

 

 

입력 :

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

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

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 21317. 징검다리 건너기
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
 
using namespace std;
 
int n, k;
vector<vector<int>> vec;
int dp[22][3];
 
 
int recur(int cur, int chance)
{
    int ret = INT_MAX;
 
    if (dp[cur][chance] != -1)
    {
        return dp[cur][chance];
    }
 
    if (cur > n) return 999999999;
    if (cur == n) return 0;
 
    // 작은 점프, 큰 점프, 매우 큰 점프 중 최소값을 찾는다.
    if (chance == 0)    // 단 매우 큰 점프는 1번만 가능
    {
        ret = min(ret, recur(cur + 3, 1) + k);
    }
    ret = min(ret, recur(cur + 2, chance) + vec[cur][1]);
    ret = min(ret, recur(cur + 1, chance) + vec[cur][0]);
 
    dp[cur][chance] = ret;
 
    return dp[cur][chance];
}
 
 
int main()
{
    cin >> n;
 
    fill(&dp[0][0], &dp[21][3], -1);
    vec.resize(n + 1, vector<int>());
 
    int a, b;
    for(int i = 1; i < n; i++)
    {
        cin >> a >> b;
        vec[i] = { a, b };
    }
    cin >> k;
 
    cout << recur(1, 0);
 
    return 0;
}
 

---

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

21317번: 징검다리 건너기