문제 설명

이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다.

삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다.

오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 경로 중 아래로만 가는 경로의 비용은 7+13+3+6 = 29가 된다. 삼각 그래프의 간선은 항상 오른쪽 그림과 같은 형태로 연결되어 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 순서대로 주어진다. 비용은 정수이며, 비용의 제곱은 1,000,000보다 작다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 테스트 케이스 번호와 아래와 같은 형식으로 출력한다.

k. n

k는 테스트 케이스 번호, n은 최소 비용이다.

문제 풀이

그래프 문제처럼 보이는 다이나믹 프로그래밍 문제이다. 열 개수가 3열로 고정되어 있고, 그에 따라 선택지도 2~4개로 줄어드므로 다이나믹 프로그래밍으로 푸는 것이 가능하다. 현재 행에서 아래쪽 줄로 내려간다고 가정할 때, 아래쪽 행의 각 노드로 향하는 화살표를 기준으로 각 노드로 이동하는 경우의 수의 최소값을 구하면 되는 간단한 문제이다. 코드는 다음과 같다.

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int idx=1;
    while(true) {
        int n; cin >> n;
        if(!n) break;
        vector<vector<int>> table(100006,vector<int>(3,0));
        for(int i=0; i<n; i++) {
            cin >> table[i][0] >> table[i][1] >> table[i][2];
        }
        vector<vector<int>> dp(100006,vector<int>(3,0));
        dp[0][0]=1000000; //0,0으론 이동이 불가능하므로 최대값을 넣어준다
        dp[0][1]=table[0][1]; dp[0][2]=table[0][2]+table[0][1];
        for(int i=1; i<n; i++) {
            dp[i][0]=min(dp[i-1][0]+table[i][0],dp[i-1][1]+table[i][0]);
            dp[i][1]=min(min(dp[i-1][0]+table[i][1],dp[i][0]+table[i][1]),min(dp[i-1][1]+table[i][1],dp[i-1][2]+table[i][1]));
            dp[i][2]=min(min(dp[i-1][1]+table[i][2],dp[i-1][2]+table[i][2]),dp[i][1]+table[i][2]);
        }//각 노드로 향하는 경우의 수의 최소값을 구해 넣어준다
        cout << idx <<". " << dp[n-1][1] << "\n";
        idx++;
    }
}