[1932] 숫자삼각형

http://boj.kr/1932

d[n][k] : n번째 줄의 k번째 숫자를 선택 했을 때, 

       1층부터 n층까지 아래로 내려오면서 더한 합의 최대값.

- 소스코드

#include <stdio.h>
#include <string.h>
 
int g[505][505];
int d[505][505];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int go(int n, int k)
{
    int L, R;
    if(n == 0 || k == 0) return 0;
 
    if(d[n][k] != -1) return d[n][k];
 
    L = go(n-1, k-1);
    R = go(n-1, k);
    return d[n][k] = g[n][k] + max(L, R);
}
 
int main()
{
    int i, j, n;
    int ans=0;
    scanf("%d", &n);
 
    for(i=1; i<=n; i++) 
        for(j=1; j<=i; j++) 
            scanf("%d", &g[i][j]);
 
    memset(d, -1, sizeof(d));
 
    for(i=1; i<=n; i++)
        ans = max(ans, go(n, i));
    printf("%d\n", ans);
 
    return 0;
}

>> 위의 줄 오른쪽 대각선의 k값은 현재 줄의 k값과 동일하며,

>> 위의 줄 왼쪽 대각선의 k값은 현재 줄의 k-1값과 동일.

>> k는 1부터 시작, g[n][0] = 0 인점을 이용.

- 아래 코드는 바텀업

#include <stdio.h>
 
int n, g[501][501], d[501][501];
 
int main()
{
    int i, j, ans;
    scanf("%d", &n);
    
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++)
            scanf("%d", &g[i][j]);
 
    d[1][1] = g[1][1];
 
    for(i=2; i<=n; i++) {
        for(j=1; j<=i; j++) {
            d[i][j] = d[i-1][j-1] > d[i-1][j] ? d[i-1][j-1] : d[i-1][j];
            d[i][j] += g[i][j];
        }
    }
 
    ans = d[n][1];
    for(i=2; i<=n; i++)
        if(ans < d[n][i])
            ans = d[n][i];
 
    printf("%d\n", ans);
    return 0;
}

>> 1년전에 푼 코드이고, 분명 직접 생각해내서 푼 기억은 있다.

>> 근데 보통 DP를 풀때 대부분의 문제를 탑다운으로 푸는데,,, 바텀업으로 풀려있다.

>> 코드의 원리는 위에서 설명한 아이디어와 동일하다.