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

문제 출처: https://www.acmicpc.net/problem/4883

4883번: 삼각 그래프

점화식을 세워 Bottom-up으로 풀었다.

arr[행][열]

점화식: 

(j == 0)dp[i][j] = min(dp[i - 1][j] + arr[i][j], dp[i - 1][j + 1] + arr[i][j]);
(j == 1)dp[i][j] = min({ dp[i - 1][j] + arr[i][j], dp[i - 1][j + 1] + arr[i][j], dp[i - 1][j - 1] + arr[i][j], dp[i][j-1]+arr[i][j] });
(j == 2)dp[i][j] = min({ dp[i - 1][j - 1] + arr[i][j], dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j] });

 

초기 값:

dp[0][0]에서는 시작할 수 없으므로 INF 값을 넣어 놓는다.

dp[0][1]은 arr[0][1]이다.

dp[0][2]에서 시작할 수는 없으나 dp[0][1] + arr[0][2]가 가능하므로 이 값으로 넣어놓는다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;


long long arr[100001][3];
long long dp[100001][3];

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int Tcount = 1;
    while (true) {
        memset(arr, 0, sizeof(arr));
        memset(dp, 0, sizeof(dp));
        int N; cin >> N;
        if (N == 0)break;


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> arr[i][j];
            }
        }

        dp[0][0] = 12345678912;
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][1] + arr[0][2];

        

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == 0)dp[i][j] = min(dp[i - 1][j] + arr[i][j], dp[i - 1][j + 1] + arr[i][j]);
                else if (j == 1)dp[i][j] = min({ dp[i - 1][j] + arr[i][j], dp[i - 1][j + 1] + arr[i][j], dp[i - 1][j - 1] + arr[i][j],dp[i][j-1]+arr[i][j] });
                else dp[i][j] = min({ dp[i - 1][j - 1] + arr[i][j], dp[i - 1][j] + arr[i][j],dp[i][j - 1] + arr[i][j] });
            }
        }
        cout << Tcount << ". ";
        cout << dp[N - 1][1]<<'\n';
        Tcount++;
        
    }

}