[21317] 징검다리 건너기

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

21317번: 징검다리 건너기

<문제>

N이 작아 브루트포스로 해결이 가능하다. 현재 상태를 나타낼때 필요한것은 아래와 같다.

int i : 위치
bool flag : 매우 큰 점프를 사용한적이 있는지
int cost : 현재까지의 비용

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, k, ans = 987654321, a[21][2];
void f(int i, bool flag, int cost) {
    if (i > n) return;
    if (i == n) {
        ans = min(cost, ans);
        return;
    }
    f(i + 1, flag, cost + a[i][0]);
    f(i + 2, flag, cost + a[i][1]);
    if (flag == false) f(i + 3, true, cost + k);
}
int main(void) {
    int i;
    cin >> n;
    for (i = 1; i <= n - 1; i++) cin >> a[i][0] >> a[i][1];
    cin >> k;
    f(1, false, 0);
    cout << ans;
    return 0;
}