[백준 4883번] 삼각 그래프 (C++)

문제링크 : https://www.acmicpc.net/problem/4883

4883번: 삼각 그래프

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N;
int graph[100000][3];
int dp[100000][3];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T = 1;

    while(1)
    {
        int N;
        cin >> N;
        if(N==0) break;
        
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<3; j++)
            {
                cin >> graph[i][j];
            }
        }  

        dp[0][0] = MAX; //사용불가 
        dp[0][1] = graph[0][1]; //시작점
        dp[0][2] = graph[0][1] + graph[0][2]; //초기값

        for(int i = 1; i < N; i++)
        {
            dp[i][0] = min({dp[i - 1][0], dp[i - 1][1]}) + graph[i][0]; //좌측
            dp[i][1] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0]}) + graph[i][1];  //중앙
            dp[i][2] = min({dp[i - 1][1], dp[i - 1][2], dp[i][1]}) + graph[i][2];  //우측
        }
    
        cout << T++ << ". " << dp[N-1][1] << "\n";
    }

    return 0;
}

시작점이 맨 첫줄의 가운데이므로, 맨 첫줄의 첫번째 값은 사용이 불가능하다.

따라서 무작위 매우 큰수를 대입시켰다.

 

이후 맨 윗줄들을 초기화 시켜주고 간단한 dp식으로 최단루트를 저장해준다.

dp식은 단순히 갈 수 있는 방향의 가장 작은 값과 해당 정점의 비용을 더한 값을 해당 정점에 저장했다.