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

문제

백준 4883 삼각 그래프 C++

4883번: 삼각 그래프

풀이

기본적인 DP문제이다.

각 행은 3열이고, 조건에 따라 열까지의 최소 거리를 저장하는 배열 dp에 따라 최소 거리를 갱신해준다.

dp 배열의 첫 행 첫 열에는 쓰레기값을 넣어주는데, 시작 지점이 따로 있으므로 첫행첫열에서 최소 거리를 갱신하지 못하게 하기 위함이다.

소스 코드

#include<iostream>
#include<algorithm>
using namespace std;
 
int graph[100001][3];
int dp[100001][3];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int caseNum = 0;
    
    while (1)
    {
        caseNum++;
        int rowNum;
        cin >> rowNum;
 
        if (rowNum == 0)
            break;
 
        for (int i = 0; i < rowNum; i++)
        {
            cin >> graph[i][0] >> graph[i][1] >> graph[i][2];
        }
 
        dp[0][0] = 987654321;
        dp[0][1] = min(graph[0][1], dp[0][0] + graph[0][1]);
        dp[0][2] = graph[0][1] + graph[0][2];
 
        for (int i = 1; i < rowNum; i++)
        {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + graph[i][0];
            dp[i][1] = min(min(dp[i - 1][0], dp[i - 1][1]), min(dp[i - 1][2], dp[i][0])) + graph[i][1];
            dp[i][2] = min(min(dp[i - 1][1], dp[i - 1][2]), dp[i][1]) + graph[i][2];
        }
 
        cout << caseNum << ". " << dp[rowNum - 1][1] << '\n';
    }
 
    return 0;
}