🖊️ 문제

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

---

🖊️ 풀이

dp지옥에 빠졌숩니다.

i번째 돌까지 최소로 에너지를 쓰면서 갈 수 있는 방법은,

일단 크게
i번째까지 슈퍼점프를 쓰면서 왔냐, 이번에 슈퍼점프를 쓰냐의 문제.

1. 슈퍼점프 안쓰는 경우
   i-1번째에서 작은 점프
   i-2번째에서 큰 점프

두 가지의 경우의 수가 있다.

2. 슈퍼점프를 써서 온 경우
   위랑 같은 경우의 수겠지만, 슈퍼점프를 써서 온 경우와 아닌 경우를 구분해줘야 한다.

3. 슈퍼점프를 지금 쓰는 경우
   i-3번째에서 슈퍼점프

슈퍼점프를 쓰는 경우와 안쓰는 경우를 구분하기 위해 dp를 int형 2차원배열로 선언했다.

그래서
앞서 말했듯이
슈퍼점프를 안쓰는 경우를 dp[i][0]
슈퍼점프를 쓰는 경우를 dp[i][1]로 했다ㅏ.

1. 슈퍼점프를 안쓰는 경우
   dp[i][0] = min(dp[i-1][0] + arr[i-1][0], dp[i-2][0] + arr[i-2][1])

2. 슈퍼점프를 써서 온 경우
   dp[i][1] = min(dp[i-1][1] + arr[i-1][0], dp[i-2][1] + arr[i-2][1])

3. 지금 슈퍼점프를 쓰는 경우
   dp[i][1] = dp[i-3][0] + k

2번과 3번에서 더 작은 경우를 dp[i][1]로 저장해주면 된다.

오류 방지를 위해 max로 각 dp를 초기화해줘야 한당.

#include <iostream>
using namespace std;

int arr[21][2];
int dp[21][2];		// [0] : 여기까지 슈점 안쓰고 옴  [1] : 여기까지 슈점쓰고 옴

int main()
{
	int n, k;
	cin >> n;

	for (int i = 1; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	cin >> k;

	for (int i = 1; i <= n; i++) {
		dp[i][0] = 5000 * 20;
		dp[i][1] = 5000 * 20;
	}

	dp[1][0] = 0;
	dp[2][0] = arr[1][0];
	dp[3][0] = min(arr[1][0] + arr[2][0], arr[1][1]);

	for (int i = 4; i <= n; i++) {
		dp[i][0] = min(dp[i - 1][0] + arr[i - 1][0], dp[i - 2][0] + arr[i - 2][1]);
		dp[i][1] = min(dp[i-3][0] + k, min(dp[i - 1][1] + arr[i - 1][0], dp[i - 2][1] + arr[i - 2][1]));
	}

	cout << min(dp[n][0], dp[n][1]) << endl;
}