[백준] 21317 - 징검다리 건너기

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

21317번: 징검다리 건너기

 

매우 큰 점프는 1번 이하로 사용할 수 있기 때문에,

dp[i][0] = 매우 큰 점프를 사용하지 않았을 때 i번째 돌에 올 수 있는 최소 에너지

dp[i][1] = 매우 큰 점프를 사용한 후 i번째 돌에 올 수 있는 최소 에너지

로 정의하고 구현하였다.

 

매우 큰 점프는 2개의 돌을 건너뛰어 이동하므로

dp[2][0] = a[1].first;

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

 

#include <iostream>
using namespace std;
int n, k, dp[30][2];
pair<int, int> a[30];
int main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	for (int i = 2; i <= n; i++) {
		dp[i][0] = dp[i][1] = 1000000000;
	}
	cin >> k;
	dp[2][0] = a[1].first;
	dp[3][0] = min(a[1].second, a[1].first + a[2].first);
	for (int i = 4; i <= n; i++) {
		dp[i][0] = min(dp[i][0], min(dp[i - 1][0] + a[i - 1].first, dp[i - 2][0] + a[i - 2].second));
		dp[i][1] = min(dp[i][1], dp[i - 3][0] + k);
		dp[i][1] = min(dp[i][1], min(dp[i - 1][1] + a[i - 1].first, dp[i - 2][1] + a[i - 2].second));
	}
	cout << min(dp[n][0], dp[n][1]);
}