(C++) - 백준(BOJ) 1932번 : 정수 삼각형

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

1932번: 정수 삼각형

dp 문제입니다.

 

 

풀이방법

d[i][j] : 현재 i행, j열로 왔을 때 최댓값입니다. i행 j열로 오기 위해서는 이전 위치가 i-1행 j-1열 또는 i-1행 j열뿐입니다. 따라서 해당위치의 최댓값 + triangle[i][j]가 답이 됩니다. 점화식으로 쓴다면,

 

d[i][j] = max(d[i-1][j-1],d[i-1][j])  + triangle[i][j]

 

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, triangle[505][505], d[505][505], ans;


int main(){
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> triangle[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            d[i][j] = max(d[i-1][j-1],d[i-1][j])  + triangle[i][j];
        }
    }

    for(int i = 1; i <= n; i++) ans = max(ans,d[n][i]);
    cout << ans;
}