BOJ 1932 - 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

1 <= i <= n, 1 <= j <= i 범위로 돌려서

dp[i][j] = max(dp[i][j] + dp[i - 1][j], dp[i][j] + dp[i - 1][j - 1]) 을 수행해주면 답이 나온다

(자기자신의 윗부분, 자기자신의 대각선 왼쪽 윗 부분 비교)

 

- c++

 

#include <bits/stdc++.h>
 
#define MAX 501
 
using namespace std;
 
int n;
int dp[MAX][MAX];
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> dp[i][j];
        }
    }
 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i][j] = max(dp[i][j] + dp[i - 1][j], dp[i][j] + dp[i - 1][j - 1]);
        }
    }
 
    int answer = -1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            answer = max(answer, dp[i][j]);
        }
    }
 
    cout << answer;
 
    return 0;
}