[Algorithm]Baekjoon 4883번 :: 삼각 그래프

https://www.acmicpc.net/problem/4883

4883번: 삼각 그래프

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int t, n;
int matrix[100001][5] = { 0 };
int dp[100001][5] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
    while (1)
    {
        cin >> n;
        if (n == 0) break;
 
        ++t;
 
        for (int i = 1; i <= n; ++i)
        {
            cin >> matrix[i][1] >> matrix[i][2] >> matrix[i][3];
        }
 
        memset(dp, 0x3f, sizeof(dp));
 
        dp[1][2] = matrix[1][2];
        dp[1][3] = matrix[1][2] + matrix[1][3];
 
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 1; j <= 3; ++j)
            {
                dp[i][j] = min({ dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1], dp[i][j-1] }) + matrix[i][j];
            }
        }
        
        printf("%d. %d\n", t, dp[n][2]);
    }
}

 

최소값을 차례차례 누적시키면 되는 어렵지않은 문제인데, 지나치기 쉬운 조건이 있다.

 

일단 반드시 첫행의 가운데정점에서 시작하고, 마지막행의 가운데정점의 최소값을 출력하는 것이다.

그리고 주어지는 각 정점의 비용은 제곱갑이 1000,000이하인 값이 주어진다. 즉, 음수가 주어질 수도 있다는 것이다.