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

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

21317번: 징검다리 건너기

문제

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

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

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

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

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

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

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

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

 

 

최소 에너지로 마지막 돌까지 건너가야한다. 전형적인 동적계획법 문제이다.

완전탐색으로 모든 경우의 수를 확인하면서 방문했던 곳은 메모이제이션으로 저장해주어 시간을 단축시켜준다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, K;
int bigE[22];
int smallE[22];
int cache[22][22][2];

void input() {
	cin >> N;
	memset(cache, -1, sizeof(cache));
	for (int i = 1; i <= N - 1; i++) cin >> smallE[i] >> bigE[i];
	cin >> K;
}

int solution(int cur, int jump, int bigJump) {
	if (cur > N) return INF;
	if (cur == N) return 0;
	int& ret = cache[cur][jump][bigJump];
	if (ret != -1) return ret;

	ret = INF;
	if (!bigJump) ret = solution(cur + 3, jump + 1, 1) + K;
	return ret = min({ ret, solution(cur + 1, jump + 1, bigJump) + smallE[cur],
							solution(cur + 2, jump + 1, bigJump) + bigE[cur] });
}

int main() {
	fastio;
	input();
	cout << solution(1, 0, 0) << endl;

	return 0;
}