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

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

문제

---

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

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

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

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

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

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

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

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

 

입력

---

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

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

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

 

출력

---

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

 

제한

---

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

문제 풀이

---

dp 문제.

 

매우 큰 점프는 한 번만 할 수 있으므로 i번째 돌까지 가는데 매우 큰 점프를 사용했음/사용하지 않았음을 나타내는 2차원 dp 배열을 만들어 해당 돌까지 가는 데 필요한 최소 에너지를 저장한다.

 

i번째 칸까지 가는 데 매우 큰 점프를 시도하지 않았다면 i-1번째 돌에서 오는 작은 점프, i-2번째 돌에서 오는 큰 점프의 경우의 수로 나뉜다.

i번째 칸까지 가는 데 매우 큰 점프를 시도했다면 i-3번째 돌까지 매우 큰 점프를 시도하지 않았지만 i-3번째 돌에서 매우 큰 점프를 시도한 경우, i-1번째 돌에서 오는 작은 점프(i-1번째 돌까지 매우 큰 점프를 시도했음), i-2번째 돌에서 오는 큰 점프(i-2번째 돌까지 매운 큰 점프를 시도했음)의 세가지 경우로 나뉜다.

이 중 가장 작은 것을 선택해 각 칸에 저장하면 된다.

 

매우 큰 점프는 돌이 3개 이상일 때 가능하므로, 돌이 2개 이하일 때 잘못된 값에 접근하지 않도록 초기화가 필요하다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N;
	int** dp = new int* [2];
	pair<int, int>* jumps = new pair<int, int>[N-1];
	for (int i = 0; i < 2; i++)
	{
		dp[i] = new int[N];
		for (int j = 0; j < N; j++)
		{
			dp[i][j] = 987654321;
		}
	}
	for (int i = 0; i < N-1; i++)
	{
		cin >> jumps[i].first >> jumps[i].second;
	}
	cin >> K;
	dp[0][0] = 0;
	dp[1][0] = 0;
	for (int i = 1; i < N; i++)
	{
		if (i == 1)
		{
			dp[0][i] = jumps[i-1].first;
		}
		else
		{
			dp[0][i] = min(dp[0][i - 1] + jumps[i - 1].first, dp[0][i - 2] + jumps[i - 2].second);
		}
		if (i >= 3)
		{
			dp[1][i] = min({ dp[0][i - 3] + K, dp[1][i - 1] + jumps[i - 1].first, dp[1][i - 2] + jumps[i - 2].second });
		}
	}
	cout << min(dp[0][N - 1], dp[1][N - 1])<<"\n";
	return 0;
}