[C/C++] 백준 1932번 - 정수 삼각형(DP)

문제에서 가장 중요한 조건은 경로를 선택할 때 대각선 왼쪽 혹은 대각선 오른쪽에 있는 것들만 선택할 수 있다는 사실이다. 브루트 포스로 모든 경우의 수를 계산할 수 있지만 효율적이지 못하며 100% 시간 초과일 것이다. (그리고 이미 DP문제인거 알고 들어왔다 ㅎ)

위의 예제 입력의 정답 경로로는 위와 같이 7 - 3 - 8 - 7 - 5 => 30이 될것이다.

 

<내가 풀이한 방법>

GIF 움짤은 처음 만들어봐서 테두리가 이상하지만 귀찮아... 담번에 제대로하지 뭐

숫자들을 입력받는 즉시 arr배열에서 위의 그림처럼 계산하고 다시 ans값으로 업데이트하는 식으로 풀이하였다.

그리하여 연산이 끝나게 되면 ans []={24, 30, 27, 26, 24}이 되는데 sorting 한 후 가장 큰 값인 30을 출력한다.

 

<DP코드>

#include <algorithm>
#include <iostream>
using namespace std;

int arr[501];
int ans[501];
int N, tmp;

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        if (i == 1)
        {
            cin >> ans[1];
            arr[1] = ans[1];
            continue;
        }
        else
        {
            for (int j = 1; j <= i; j++)
            {
                cin >> tmp;

                if (j == 1)
                {
                    arr[j] = tmp + ans[1];
                }
                else if (j == i)
                {
                    arr[j] = tmp + ans[j-1];
                }
                else
                {
                    arr[j] = tmp + max(ans[j - 1], ans[j]);
                }
            }

            for (int k = 1; k <= i; k++)
            {
                ans[k] = arr[k];
            }

        }
    }

    sort(ans + 1, ans + 1 + N, greater<int>());

    cout << ans[1];

}

 

 

 

 

DP도 풀다 보면 익숙해지는 것 같다 *^^*

 

 

www.acmicpc.net/problem/1932

1932번: 정수 삼각형