[C++]백준 - 1932번 문제

1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

 

1932번 : 정수 삼각형

---

 

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

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

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

 

입력

---

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

맨 아래에서 부터 위 쪽 방향으로, 더하면서 올라갈 때, 가장 큰 값을 가지는 부분을 동적 계획법(dp) 배열로 저장하면서 올라갑니다.

 

예시)

 

n=0        1

n=1     2     3

 

tri[n][k] = 정수 삼각형의 n번째 행, k 번째 숫자

-> dp[0][0] = tri[0][0] + max(dp[1][0], dp[1][1])

 

위와 같은 방법을 고려하면,

=> dp[n][k] = tri[n][k] + max(dp[n+1][k], dp[n][k+1])

 

위와 같은 식을 사용하여, 최종적으로는 dp[0][0]이 답이 됩니다.

 

코드

---

#include <iostream>
using namespace std;
int tri[500][500] = {0, };
int dp[500][500] = {0, };

int solution(int level, int N, int k)
{
    if(level == N) return 0;

    if(dp[level][k] == 0)
    {
        int ret = solution(level + 1, N, k);
        int ret_b = solution(level + 1, N, k + 1);
        if(ret < ret_b) ret = ret_b;
        dp[level][k] = ret + tri[level][k];
    }
    return dp[level][k];
}


int main()
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i+1; j++) cin >> tri[i][j];
    }
    
    cout << solution(0, N, 0);
    
    return 0;
}

 

그 외

---