BOJ 1932 - 정수 삼각형

pa324·2019년 11월 10일
0

문제

풀이

위층부터 시작해서 가장 아래층 까지 내려갈때, 합이 최대가 되도록 내려가는 경로를 찾아야 하는 문제이다. (단, 내려갈때 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능하다.)

아래와 같은 형태로 삼각형이 주어졌다고 생각해보자.

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

먼저, 계속해서 왼쪽으로만 내려오는 경우를 생각할 수 있고, 계속해서 오른쪽으로만 내려가는 경우를 생각할 수 있다. 예를들면 7->3->8->2-4, 7->8->0->4->5가 있다. 이를 수식으로 표현하면 dp[i][j] = dp[i-1][j], dp[i][j] = dp[i-1][j-1]이 된다. 왼쪽으로만 내려가는 경우는, 현재 인덱스와 같은 값을 더하고, 오른쪽으로만 내려가는 경우는 현재 인덱스보다 1작은 값에서 자기 자신을 더하는방식이다. 그렇다면 양쪽 끝으로만 내려오는 경우가 아니라, 7->3->1 과 같이 다른 경로를 택하는 경우는 어떻게 구할까? 결국 왼쪽 위에서 자신으로 내려오거나, 오른쪽 위에서 자신으로 내려오는 경우 중 큰값을 선택하면 된다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[501][501];
int ans = -2147000000;
int main() {
    
    int n;
    scanf("%d",&n);
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <=i; j++) {
            scanf("%d",&dp[i][j]);
        }
    }
    
    
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(j == 1) dp[i][j] += dp[i-1][j];
            else if(j == n) dp[i][j] += dp[i-1][j-1];
            else dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
        }
    }
    
    for(int i = 0; i < n; i++) {
        if(dp[n][i] > ans) ans = dp[n][i];
    }
    
    printf("%d",ans);
}
profile
안녕하세요

0개의 댓글