[백준/C++] 1932번 정수 삼각형

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

1932번: 정수 삼각형

오랜만에 푼 DP(다이나믹 프로그래밍)문제다.

우선 삼각형을 입력 받아준다. 입력값들의 길이가 1,2,3,... 순으로 증가하므로 2차원 벡터를 이용해 입력 받았다.

그런 다음, 초기값을 설정해주는 것이 중요한데 dp[1][0]은 삼각형의 맨 첫번째 값(=꼭대기 값)이고 dp[1][1]은 원래 존재하지 않는 값이지만 점화식을 생성 및 이용하기 위해 0으로 설정해주었다.

초기값(삼각형 1층)에 대한 설정이 끝났으므로, 그 아래 줄인 삼각형 2층부터 점화식을 이용해 최대값을 저장해주면 된다.

다만, 맨 왼쪽은 항상 바로 위의 값과 더해짐을 유의해주자.

​

또한 dp배열을 main문 바깥에 정의하였기 때문에 이 배열은 자동으로 0으로 초기화 된다. 때문에 맨 오른쪽 값을 더할 때, 범위가 벗어나도 그 값이 0이므로 지장이 없는 것! 이해가 안된다면 아래 사진을 보자

​

점화식에 대해 설명하자면, DP는 보통 직전에 구한 값들이 다음 값 계산에 영향을 미친다. 그렇기 때문에 dp 배열에는 그 순간 순간 마다의 최댓값을 저장해놓으면 된다

​

문제의 예제중 일부를 살펴보자.

위 그림처럼 dp 배열에는 각 층에서 가질 수 있는 최댓값을 저장해주는 것이다!

여기서 16이란 수는 10(7+3) +1 과 15(7+8)+1 중 최댓값을 선택한 것이다.

#include <iostream>
#include <vector>

typedef long long ll;
using namespace std;

int n,num;
vector<int> v[510];
int dp[510][510];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for(int i=1; i<=n;i++){
        for(int j=1; j<=i;j++){
            cin >> num;
            v[i].push_back(num);
        }
    }
    dp[1][0] = v[1][0];
    dp[1][1] = 0;

    for(int i=2;i<=n;i++){
        dp[i][0] = dp[i-1][0] +v[i][0];
        for(int j=1; j<v[i].size();j++){
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + v[i][j];
        }
    }
    int ans=-1;
    for(int i=0; i<v[n].size();i++){
        ans = max(ans,dp[n][i]);
    }
    cout << ans;
}