21317 징검다리 건너기

징검다리 건너기 문제

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

대표적인 스킬이 있는 dp 문제

유사 문제로 징검다리 건너기2가 있음

1. 문제

---

간단 설명

세가지 점프 방법이 있다

1. 작은 점프 : N에서 N+1로 한칸 이동
2. 큰 점프 : N에서 N+2로 두칸 이동
3. 매우 큰 점프 : N에서 N+3으로 세칸 이동

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

매우 큰 점프는 단 한 번만 사용 가능 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지 에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하기

매우 큰 점프를 점화식에서 어떻게 표현할 것인가가 포인트

2. 문제 분석

---

필요변수

돌의 개수 N

1번 돌부터 N-1번 돌까지 작은 점프와 큰점프에 들어가는 에너지를 저장하는 배열 jump[N][2]

매우 큰점프에 사용되는 에너지 K

N까지 도달하는데 필요한 에너지의 최소값을 저장할 2차원 배열 DP[N][2] N : 돌 x까지 가는데 필요한 최소한의 에너지 2 : 매우 큰 점프의 사용 유무 (0, 1)

주의점

• 수동으로 dp를 어디까지 채울것인지
• 매우 큰 점프 사용을 어떻게 처리할 것인지가 중요

알고리즘

1. N 입력받고 N-1개의 작은 점프, 큰점프 에너지 입력받기, K 입력받기
2. dp 배열을 최대값으로 초기화
3. 점화식을 세울 수 없는 dp[0][0], dp[1][0], dp[2][0]의 초기값 입력
4. 점화식을 이용하여 N-1까지 DP 채우기
5. 마지막에 저장된 값 중 더 작은 값을 출력

점화식

dp[x][0] = min( 
    x-1번째 돌의 작은 점프 에너지 + dp[x-1][0], // x-1에서 작은 점프 하거나
    x-2번째 돌의 큰 점프 에너지 + dp[x-2][0] // x-2에서 큰점프 하거나
    )

// 매우 큰 점프를 사용한 경우 dp[i][0] 에서 dp[i+1][1] 로 이동하게됨
dp[x][1] = min( // 3개중 최소값을 비교해야함
    x-1번째 돌의 작은 점프 에너지 + dp[x-1][1], // x-1에서 작은 점프 하거나
    x-2번째 돌의 큰 점프 에너지 + dp[x-2][1], // x-2에서 큰점프 하거나
    K + dp[x-3][0] // x-3에서 매우 큰 점프를 하거나
    )

3. 소스코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	// 1. 입력받기
	int N, K;
	int jump[21][2] = { 0 };
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		cin >> jump[i][0] >> jump[i][1];
	}
	cin >> K;

	// 2. dp 초기화
	int dp[21][2];
	for (int i = 0; i < N; i++) {
		fill(dp[i], dp[i] + 2, 21e8);
	}
    // 3. 점화식을 세울 수 없는 dp 값 수동으로 채우기
	// 시작지점 코스트는 0
	dp[0][0] = 0; 

	// 1로 도달하는 방법은 시작지점에서 한칸 건너는것밖에 없음
	dp[1][0] = dp[0][0] + jump[0][0];

	// 2로 도달하는 방법은 (1에서 2로 작은 점프하는 방법), (0에서 2로 큰점프 하는 방법) 중 최소값
	dp[2][0] = min(dp[1][0] + jump[1][0], dp[0][0] + jump[0][1]);

    // 4. 점화식을 이용해 dp 값 채우기
	// 3번째부터 N-1에 도착할때까지 dp 채우기
	for (int i = 3; i < N; i++) {
		dp[i][0] = min(dp[i - 1][0] + jump[i - 1][0], dp[i - 2][0] + jump[i - 2][1]);
		dp[i][1] = min({
			dp[i - 1][1] + jump[i - 1][0], 
			dp[i - 2][1] + jump[i - 2][1], 
			K + dp[i - 3][0], // i-3에서 매우 큰점프 사용하거나
			});
		// C++11 이후 부터는 min({ 1,2,3 }) 으로 3개 이상의 최대 최소값을 한번에 구할 수 있음!
	}

    // 5. 마지막에 도달했을 때, 최소값을 비교해서 더 작은값 출력
	cout << min(dp[N - 1][0], dp[N - 1][1]);

	return 0;
}