[백준 4883번] 삼각 그래프

소스코드

---

#include <iostream>
using namespace std;
 
int Min(int a, int b) {
    return a > b ? b : a;
}
 
int main() {
    int n, dp[100001][3], tc = 1;
    while (1) {
        cin >> n;
        if (!n)
            break;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> dp[i][j];
            }
        }
        
        dp[1][0] = dp[1][0]+dp[0][1];
        dp[1][1] = Min(dp[1][1]+dp[1][0],Min(dp[0][1]+dp[0][2]+dp[1][1], dp[1][1]+dp[0][1]));
        dp[1][2] = Min(dp[1][1]+dp[1][2], Min(dp[1][2] + dp[0][1], dp[1][2]+dp[0][1]+dp[0][2]));
 
        for (int i = 2; i < n; i++) {
            dp[i][0] += Min(dp[i - 1][0], Min(dp[i - 1][1],dp[i-1][1]));
            dp[i][1] += Min(Min(dp[i][0],dp[i-1][0]), Min(dp[i-1][2],dp[i-1][1]));
            dp[i][2] += Min(dp[i][1], Min(dp[i - 1][2], dp[i - 1][1]));
        }
        cout << tc++ << ". " << dp[n-1][1] << '\n';
    }
    return 0;
}