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

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

21317번: 징검다리 건너기

쉬운문제인데 C++ 공부를 위해 풀었다.

현재 단계에 있는 모든 돌들을 확인하면서 다음 단계를 추가하고 가장 마지막에 있는 돌에서 최솟값을 찾는 방식으로 풀었다.

#include<iostream>
#include<vector>
using namespace std;

int find_energy(int n, int super_jump, int jump[20][2]) {
	int i, j, cur, cur_chance, ret;
	vector<pair<int, int>> memo[20];
	memo[0].push_back(make_pair(0, 1));
	for (i = 0; i < n; i++)
	{
		//cout << memo[i].size() << endl;
		for (j = 0; j < memo[i].size(); j++)
		{
			cur = memo[i][j].first;
			cur_chance = memo[i][j].second;
			if (i + 1 < n)
			{
				memo[i+1].push_back(make_pair(cur + jump[i][0], cur_chance));
			}
			if (i + 2 < n) {
				memo[i+2].push_back(make_pair(cur + jump[i][1], cur_chance));
			}
			if (cur_chance && i + 3 < n) {
				memo[i+3].push_back(make_pair(cur + super_jump, 0));
			}
		}
	}
	ret = 200000;
	for (i = 0; i < memo[n-1].size(); i++)
	{
		if (ret > memo[n - 1][i].first)
			ret = memo[n - 1][i].first;
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n, i, j, k;
	int jump[20][2];
	cin >> n;
	for (i = 0; i < n - 1; i++)
	{
		cin >> jump[i][0] >> jump[i][1];
	}
	cin >> k;

	cout << find_energy(n, k, jump);

	return 0;
}