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

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

1932번: 정수 삼각형

 

#include <iostream>
#include<string>
#include<math.h>
#include<istream>
#include<algorithm>
using namespace std;
 
int dp[501][501];
int arr[501][501];
 
 
 
int main() {
 
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int num;
            cin >> num;
            arr[i][j] = num;
        }
    }
 
    dp[0][0] = arr[0][0];
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1) {
                dp[i][j] = dp[i - 1][1] + arr[i][j];
            }
            else if (j == i) {
                dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
            }
        }
    }
    int maxNum = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[n][i] > maxNum) {
            maxNum = dp[n][i];
        }
    }
    cout << maxNum << endl;
 
 
 
 
}

 

문제를 풀면서 중요한 것은 양 끝 가장 자리를 신경써주는것이다. 이거 때문에 여러번 틀렸습니다가 나왔다.

예를 들어 dp[2][0]의 경우 dp[1][0]+arr[2][0]만 가능하다. 왜냐면 얘는 오른쪽 위에서만 올 수 있지 왼쪽 위는 원소가 없기 때문이다. 반대로 dp[2][2]의 경우 dp[1][1]+arr[2][2]만 가능하다.  얘는 왼쪽 위에서만 올 수 있지 오른쪽 위는 원소가 없기 때문이다. 

그리고 진짜 최대값은 맨 마지막 줄 즉 dp[n][1]~dp[n][n]까지의 값 중 가장 큰 애를 출력해주면 된다. 

잘못 생각한 부분 

우선 dp식을 세울 때 dp의 관점이 아니라 arr의 관점에서 세워버렸다.. 반드시 dp의 관점에서 세울 것 그리고 위에서 아래로 내려가면서 아래에 있는 원소 중 더 큰 애를 더해주는 것(arr[i]값->arr의 관점) 보다 아래에서 위를 바라봤을 때 더 큰 값(사실상 더 큰 누적합 값, dp[i]값 ->dp의 관점)  구하는게 훨씬 편하다. 

그렇기에 이런 망 코드가 생겨났다. dp[i]처럼 i행까지 더했을 때 최대가 되는 경우를 dp[i]에 더하는게 아니라

dp[i][j]처럼 i행 j열까지 오는데 최대가 되는 경우를 dp[i][j]에 저장하고 마지막에 max를 돌리면 된다. 

아 그러면 dp의 관점에서 바라본다는 것이 무엇일까?

 

arr이

 

7

3  8

8  1  0  이 있을 때 dp의 관점에서 누적합으로 배열을 만들어보면

 

7

10  15

18  16(11과 16중에 더 큰 값이 16)  15

로 만들어 낼 수 있다. 그렇기에 dp의 관점으로 식을 세울 땐 위-> 아래로 아래에 있는 원소 중 더 큰 값을 구별해주는 것보다 , 아래 -> 위를 바라보면서 우선 기준이 되는 아래의 원소를 더해주고 아래의 원소 기준으로 왼쪽 위/ 오른 쪽 아래의 값중 더 큰  dp값(누적합 값)을 더해주면 되는 것이다.