[DP] 백준 1932 숫자삼각형

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

유형은 거의 비슷했고 max안에서 d[i-1][j-1]을 d[i-1][j+1]로 생각해서 조금 해맸었다. 

감으로 하지말고 종이로 생각하면서 하니까 문제점을 찾을 수 있었다. 

메모리랑 시간이 좀 효율적이지 못하다는 것을 보여주는데 나중에 배열을 덜 쓰던가 해서 수정해 보자.

#include <iostream>

#define max(a,b) ((a)>(b) ? (a) : (b))

using namespace std;

int d[501][501];

int sample[501][501];

int main() {

        int n;

        cin >> n;

        for (int i = 1; i <= n; ++i) {

               for (int j = 1; j <= i; ++j) {

                       cin >> sample[i][j];

               }

        }

        d[1][1] = sample[1][1];

        for (int i = 2; i <= n; ++i) {

               for (int j = 1; j <= i; ++j) {

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

               }

        }

        int ans = 0;

        for (int j = 1; j <= n; ++j) {

               if (ans < d[n][j])

                       ans = d[n][j];

        }

        cout << ans;

        return 0;

}