[백준] 1932번 정수 삼각형 | Miran Lee 👩‍💻

DP(Bottom-up, Top-down)

문제

        7
 8
 1   0
 7   4   4
 5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

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

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

풀이

Bottom-up 풀이 1

항상 내가 DP를 풀던 방식은 Bottom-up이었다. 그래서 이 문제도 Bottom-up방식으로 풀었다 처음에는 위의 삼각형에서 부모(7)로부터 자식(3,8) 각각에게 부모의 최댓값(dp)을 주어 저장하고 이 최댓값과 새로운 부모로부터 받게되는 값을 비교해 큰 값을 저장한다. 그러하면 바깥 for문은 n-2번을 돌면서 n-1번째 배열에 최댓값들이 저장되므로 그 중에서의 최댓값을 반환하는 알고리즘으로 설계했다. 그런데 답도 출력이 잘되고 알고리즘에 문제가 없는데 시간초과가 뜨는 것이다.

Bottom-up 풀이 2

그래서 알고리즘이 잘못됐나 하고 새로 짠 코드다. 위의 코드는 부모가 기준이고 자식들에게 값을 각각 줬다면, 이 풀이는 자식을 기준으로 각각의 부모로부터 값을 받아온다. 세번째 줄의 1처럼 3,8로부터의 중복된 연산을 줄이는 코드였다. 각 줄의 첫번째와 마지막 코드 예외처리만 하고 나머지는 부모의 최댓값만 받아오면 된다. 그런데 이 코드도 시간초과가 뜨는 것이었다. 문제를 잘못 읽은 건지 MAX가 500인데 300으로 줘서 풀이 두개다 시간 초과가 났던 거였다. 너무.. 허탈.. 바보같은 실수.. 그래서 어쩌다 두가지의 풀이가 탄생하게 되었다. 물론 두개다 MAX를 변경하니 통과되었다.

Top-down

야심차게 DP 이론 정리를 해서 top-down의 존재를 알아버렸으니 top-down으로도 풀어보았다. 틀은 DP개념정리에서의 피보나치 TOP-DOWN과 똑같다. 여기서 기저사례랑 점화식만 문제에 맞게 변경해주면 된다. 하지만 또 다른 고려 조건이있다. 아래 코드에서

if(dp[i][j])
return dp[i][j];

이 부분이 있다. 이 부분은 dp에 값이 존재하면 연산을 하지 않고 해당 값을 반환해주는 코드이다. 이 부분 때문에

  0
 0 0
0 0 0 

이 반례를 통과하지 못한다. 따라서 기존의 삼각형의 초기값을 -1로 설정해주고

if(arr[i][j]==-1)
return 0;

이 부분을 추가해주어 해결하였다. 질문 게시판에 똑같은 코드가 있어서 문제를 해결할 수 있었다 ㅠㅠ 풀다보니 이 문제는 top-down 방식보단 bottom-up이 훨씬 간단한 것같았다. 괜히 top-down으로도 풀어보겠다고..다른 좋은 예제들도 있는데 사서 고생했다. 그래도 처음으로 dp를 top-down으로 풀어보았다.

코드

사용언어: C++

Bottom-up 풀이 1

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAX 501 //문제의 MAX...
int arr[MAX][MAX];
int dp[MAX][MAX];

int DP(int n)
{
    dp[0][0] = arr[0][0];

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + arr[i + 1][j]); //왼쪽 자식에게 값을 부여
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + arr[i + 1][j + 1]); //오른쪽 자식에게 값을 부여
        }
    }

    return *max_element(&dp[n - 1][0], &dp[n - 1][n]);///마지막 줄에서 최댓값 반환
}

int main()
{
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i + 1; j++)
            scanf("%d", &arr[i][j]);
    }

    cout << DP(N) << endl;
}

Bottom-up 풀이 2

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 501
int arr[MAX][MAX];
int dp[MAX][MAX];

int DP(int n)
{
    dp[0][0] = arr[0][0];

    int dp_max = dp[0][0];

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            if (j == 0) //첫번째 원소인 경우(부모가 중복되지 않음)
                dp[i][j] = dp[i - 1][j] + arr[i][j];
            else if (j == i) //마지막 원소인 경우(부모가 중복되지 않음)
                dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
            else //중복된 부모를 가진 경우
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
        }
    }

    return *max_element(&dp[n - 1][0], &dp[n - 1][n]);
    //마지막 줄에서 최댓값 반환
}

int main()
{
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i + 1; j++)
            scanf("%d", &arr[i][j]);
    }

    cout << DP(N) << endl;
}

Top-down

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAX 501
int arr[MAX][MAX];
int dp[MAX][MAX];

int DP(int i, int j)
{
    if (i == 1)
        return arr[1][1];
    if (arr[i][j] == -1) //반례)모두 0인 경우를 위해
        return 0;
    if (dp[i][j]) //값이 존재한다면 
        return dp[i][j];
    dp[i][j] = max(DP(i - 1, j), DP(i - 1, j - 1)) + arr[i][j]; //이전 줄의 부모들 호출
    return dp[i][j];
}

int main()
{
    int N, temp, max = -1;
    scanf("%d", &N);
    memset(arr, -1, sizeof(arr));
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
            scanf("%d", &arr[i][j]);
    }

    for (int i = 1; i <= N; i++) //마지막 줄에서 시작(top-down)
    {
        temp = DP(N, i);
        if (temp > max) //마지막 줄에서의 최댓값 찾기
            max = temp;
    }
    cout << max << endl;
}

출처

백준