백준 1932 정수삼각형

문제

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

설명

이것은 문제는 삼각형으로 되어있는데 예제를 보면 직각삼각형태로 볼 수 있다

• 격자 안에서 한 칸씩 전진하는 DP

• 직각 삼각형이 있을때 얻을 수 있는 최대값 맨 윗행부터 시작해서 r +1, c로 가거나 r +1, c + 1로 이동할 수 있다

• dp[i][j] - > 마지막 방문한 위치를 (i, j)에서 얻을 수 있는 최대 값

• dp[i][j] = max(dp[i-1][j] + a[i][j], dp[i-1][j-1] + a[i][j])

주의할점

저는 top - down으로도하고 tabulation으로도 해결해보았습니다
top-down일때문제는 범위를 x - 1 <0 || y -1 < 0로 해서 틀렸는데 이부분을
x < 0 || y < 0 으로 해결하였고 또한 초기화 문제를 왜 해주어야하는지 고민이었다
dp[0][0]만 해주면 되지 않을까 그렇지 않다

만약 그렇게 한다면 if (x < 0 || y < 0) return 0 이부분에서 막혀서 안될것이다.

소스

#include <bits/stdc++.h>

using namespace std;



// max(dp[n-1][j]) 
int n;
int dp[501][501];
int a[501][501];

void Print() {
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j];
        }
        cout << endl;
    }
}
void inital() {
    dp[0][0] = a[0][0];

    for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + a[i][0];

    //대각석은 i, i 1,1 2, 2 ..- > ..
    for (int i = 1; i < n; i++) dp[i][i] = dp[i - 1][i - 1] + a[i][i];
}

int solve(int x, int y) {

    // 이부분때문에 두가지 조건을 모두 충족해야하기 때문에 -> 일자로 내려온는부분, 대각선으로 가는 부분 초기화해주어야한다 
    if (x < 0 || y < 0) return 0;

    if (dp[x][y] != -1) return dp[x][y];

    dp[x][y] = max(solve(x - 1, y), solve(x - 1, y - 1)) + a[x][y];
    return dp[x][y];
}
int main() {

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++) {
            cin >> a[i][j];
        }
    }
    //Print();
    //dp초기화 
    memset(dp, -1, sizeof(dp));
    inital();
    int ans = 0;

    for (int i = 0; i < n; i++) {
        ans = max(ans, solve(n - 1, i));
    }
    cout << ans;
    return 0;
}