[C++] 백준 1932번 : 정수 삼각형 (S1)

#문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

#풀이 & 학습한 내용

삼각형 내부의 어떤 수 기준으로 볼때 윗열에서 오는 수는 왼쪽에서 연결되거나 오른쪽에서 연결된다. "삼각형 내부의 i행 j열 위치에서 그 위치까지 연결된 합 중 최대"를 dp[i][j]이라 할 때, dp[i][j] = max({ dp[i - 1][j - 1], dp[i - 1][j] }) +p[i][j]인 substructure를 얻을 수 있다. 이를 토대로 for문을 구성하여 dp배열을 n까지 채운다. 그리고 마지막에 dp배열의 n행에 있는 값들 중 최댓값을 답으로 출력한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[501][501];
int dp[501][501];
 
int main(void) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> p[i][j];
 
    dp[1][1] = p[1][1];
    for (int i = 2; i <= n; i++) {
        dp[i][1] = dp[i - 1][1] + p[i][1];
        for (int j = 2; j < i; j++) {
            dp[i][j] = max({ dp[i - 1][j - 1], dp[i - 1][j] }) +p[i][j];
        }
        dp[i][i] = dp[i - 1][i - 1] + p[i][i];
    }
 
    int max = -1;
    for (int i = 1; i <= n; i++) {
        if (max < dp[n][i])
            max = dp[n][i];
    }
    cout << max << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_1932.cpp

HoYoungChun/BOJ_algorithm