2017년 3월 3일 금요일

1932 숫자삼각형

백준 1932 숫자삼각형 https://www.acmicpc.net/problem/1932

다음과 같은 규칙을 만족해야 한다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

여기서 샘플을 이용하여 문제를 따라가면 중첩되는 부분을 알 수 있다.
층에서 내려올때의 경우의 수를 먼저 구해보자
경우의 수는 7,3,8/ 7,3,1/ 7,8,1/ 7,8,0 이 나오는데 문제에서는 최대 경로를 구하는 것이므로 이중에서 가운데 있는 부분(3층의 숫자1)은 2가지경우중 더 큰곳에 대해서만 Memoization해 놓으면 된다.

따라서 층입력이 500까지 되므로 cache를 500 * 500 공간으로 잡아서 DP를 시행하면 된다.
DP를 정의하자면
DP[N][M]  : N층 M번째 숫자 까지의 최대 경로

DP[N][1] = DP[N-1][1] + Floor[N][1]
DP[N][N] = DP[N-1][N-1] + Floor[N][N]

for(i = 2; i < N; i++)
     DP[N][i] = max(D[N - 1][i - 1], D[N - 1][i]) + Floor[N][i];


#include <cstdio>
#define max(a,b) ((a>b)?a:b)
int arr[501][501];
int D[501][501];
int main(){
    int N, ans = 0;
    scanf("%d"&N);
 
    for (int n = 1; n <= N; n++){
        for (int m = 1; m <= n; m++){
            scanf("%d"&arr[n][m]);
        }
        if (n == 1)
            D[1][1= arr[1][1];
        else{
            D[n][1= D[n - 1][1+ arr[n][1];
            D[n][n] = D[n - 1][n - 1+ arr[n][n];
            ans = max(D[n][1], D[n][n]);
            for (int k = 2; k < n; k++){
                D[n][k] = max(D[n - 1][k - 1], D[n - 1][k]) + arr[n][k];
                if (n == N)
                    ans = max(ans, D[N][k]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
cs

댓글 없음:

댓글 쓰기