백준 21317, 징검다리 건너기

개요

문제 링크
실버 1, DP

1회까지 사용가능한 특수이동을 고려해 최소 비용 경로 구하기

---

접근

1. 1회까지만 사용가능한 특수이동이 존재하므로 dp는 2차원, dp[i][0] = 사용안하고 i까지, dp[i][1] = 사용하고 i까지
2. 나머지는 단순 2차원 dp, 1,2,3칸 이전의 값과 연산해주면 된다.
   주의할 점 : 음수 인덱스 접근 안하도록 확인

---

Pseudo code

dp[i][0] = 특수이동 없이 i까지 온 경우
dp[i][1] = 특수이동 쓰면서 i까지 온 경우

// 특수이동 없는 경우
한칸전에서이동 = dp[i-1][j] + (+1)비용
두칸전에서이동 = dp[i-2][j] + (+2)비용
dp[i][j] = min(한칸전에서이동, 두칸전에서이동)
// j인 이유 = 특수이동을 쓴 경우와 안 쓴 경우 모두 +1, +2은 쓸 수 있음

// 특수이동 해서 온 경우
세칸전에서 이동 = dp[i-3][0] + ((+3)비용 = k)
dp[i][1] = min(dp[i][1], 세칸전에서이동);

---

Source code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n;
    int a[n][2];
    for (int i=1; i<=n-1; i++)
        cin >> a[i][0] >> a[i][1];
    cin >> k;
    int dp[n+2][2];
    dp[1][0] = 0;
    dp[1][1] = 0;
    for (int i=2; i<=n; i++) {
        dp[i][0] = dp[i-1][0]+a[i-1][0];
        dp[i][1] = dp[i-1][1]+a[i-1][0];
        if (i<=2) continue;
        dp[i][0] = min(dp[i][0], dp[i-2][0]+a[i-2][1]);
        dp[i][1] = min(dp[i][1], dp[i-2][1]+a[i-2][1]);
        if (i<=3) continue;
        dp[i][1] = min(dp[i][1], dp[i-3][0]+k);
    }
    cout << min(dp[n][0], dp[n][1]);
}