1932번 정수삼각형

문제 링크 : https://www.acmicpc.net/problem/1932

해결 방법 :

제일 단순하게 처음 시도했던 방법은 완전탐색으로 왼쪽합누적, 오른쪽 합누적 하는 방법으로 n번째 줄까지 전부 구했었다.

그리고 n번째줄에서 모든 합들을 비교해서 최대값을 찾아서 출력했었는데, 시간초과로 틀렸었다. 알고보니 2의 n승의 시간복잡도....ㅜ

그래서 다이나믹프로그래밍의 메모이제이션 기법을 사용해야겠다는 생각을 했다. 왜냐 시간초과니까 ㅜ

시간을 줄일방법을 생각해보니까 재귀를 줄여야겠다고 생각했다.

재귀를 줄이려면 각각의 요소가 최대값을 가져야했고 그거를 재호출했을때 미리 저장해놓은 최대값을 툭 내뱉어버리면 다시 재귀호출을 안할수 있다고 생각했다.

그래서 n번째 줄에서 부터 거꾸로 찾아나갔다. (top-down 방식)

n번째줄의 i번째 요소까지의 최대값은 max(n-1번째줄의 i번째 최대값, n-1번째줄의 i-1번쨰 최대값) + n번쨰줄의 i번째요소값 의 점화식으로 구할 수 있었다.

그리고 이를 기록해야한다. 왜? 재호출 방지위해서

식으로보면, d[x][y] = max(solve(x-1,y), solve(x-1,y-1)) + a[x][y] 이다.

또한, -1은 범위밖에있는 것들을 미리 저장해놔서 그곳에 호출하려하면 0을 리턴한다.  왜냐? 존재하지 않는 값이니까..

#include<iostream>
using namespace std;
int d[501][501];
int a[501][501];
int N;
int Max2 = -1;
int solve(int x, int y)
{
    if(x==1 && y==1)
    {
        return a[1][1];
    }
    if(a[x][y] == -1)
    {
        return 0;
    }
    if(d[x][y]) return d[x][y];
    d[x][y] = max(solve(x-1,y), solve(x-1,y-1)) + a[x][y];
    return d[x][y];
}
int main()
{
    scanf("%d",&N);
    int Max;
    for(int i = 0; i<=N; i++)
    {
        for(int j = 0; j<=N; j++)
        {
            a[i][j] = -1;
        }
    }
    for(int i = 1; i<=N; i++)
    {
        for(int j = 1; j<=i; j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i =1; i<=N; i++)
    {
        Max = solve(N,i);
        if(Max > Max2)
        {
            Max2 = Max;
        }
    }
    printf("%d",Max2);
}