정수 삼각형

04 May 2021

Reading time ~1 minute

백준 1932 - 정수삼각형 (https://www.acmicpc.net/problem/1932)

풀이

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[501][501];
int dp[501][501] = {0};
 
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> arr[i][j];
        }
    }
    
    dp[1][1] = arr[1][1];
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];
        }
    }
    int max = 0;
    for(int i = 1; i <= n; i++){
        if(max < dp[n][i])
            max = dp[n][i];
    }
    
    cout << max << '\n';
    
    return 0;
}

추가로 가져갈것

최대값 구하는 알고리즘 따로 기억

    int max = 0;
    for(int i = 1; i <= n; i++){
        if(max < dp[n][i])
            max = dp[n][i];
    }