[ 백준 1932 ] 정수 삼각형 (C++)

백준의 정수삼각형(1912) 문제이다.

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 보다 상세한 설명을 다시 포스팅 해놓았습니다. 이 글을 읽으셔도 무관하지만, 보다

  구체적인 설명을 원하시는 분들은 아래의 링크를 타고 가시면 됩니다 ! )

   [ 백준(1912) 정수 삼각형 ]

[ 문제설명 ]

- 입력으로 삼각형의 높이와, 각 삼각형의 높이에 들어가는 숫자들을 입력받게 된다.

- 1층(가장 꼭대기 층을 의미)에는 1개, 2층에는 2개, N층(가장 아랫층)에는 N개의 숫자들이 들어가게 된다.

- 1층에서부터 N층까지 내려오는데, 내려올 때에는 왼쪽 대각선 아래 혹은 오른쪽 대각선 아래로만 내려올 수 있다.

- 주어진 삼각형에서 나올 수 있는 최댓값을 구하면 된다.

[ 문제풀이 ]

1) 먼저 본인은 2차원 배열을 2개 사용했다. 삼각형의 정보를 저장하는 Arr[][] 2차원 배열과, 최댓값을 저장하는

   DP[][] 2차원 배열을 사용했다.

2) Arr[a][b]의 의미는 ' a층에서 b번째 숫자 ' 를 의미한다. 당연히 Arr[1][2], Arr[1][3]의 값은 존재하지 않을 것이다.

3) DP[a][b]의 의미는 ' a층의 b값을 선택했을 때의 최댓값 ' 을 의미한다. 

4) 먼저, 사용하지 않는 배열들에 대한 정리 및 초기식을 구해보면

   Arr[0][0] , [0][1] , [1][0] , DP[0][0] , [0][1], DP[1][0] 는 0이 될것이다. 왜냐하면 본인은 0층을 사용하지 않았고,

   삼각형의 각 층의 숫자들을 표시할 때도, 0번째 숫자는 없기 때문이다.

    1

  2  3 이렇게 있으면 1 = Arr[1][1] , 2 = Arr[2][1] , 3 = Arr[2][2] 로 표시하였다.

5) DP[1][1]의 값은 Arr[1][1]이 될것이다. (1층의 첫 번째 숫자를 선택했을 때의 최댓값 = 1층의 첫 번째 숫자)

6) 여기서 삼각형의 형태를 잘 생각해보면, 정삼각형의 형태로 주어지고, 1번째 숫자가 내려올 수 있는 곳은 1,2번 2곳이 있고

   2번째 숫자의 경우 2,3번, ... , a번째 숫자의 경우 a, a+1번이 있게 된다.

   ex) 

        1

     2    3

   4    5    6  이러한 삼각형이 있을 때, 숫자 '2'는 2층에 1번째 숫자이고, 내려올 수 있는 숫자는 '4' , '5'가 있다.

                  '4'는 3층에 1번째 숫자이고, '5'는 3층에 2번째 숫자이다. 

                 숫자 '3'은 2층에 2번째 숫자이고, 내려올 수 있는 숫자는 '5', '6'이 있다.

                  '5'는 3층에 2번째 숫자이고, '6'은 3층에 3번째 숫자이다.

    즉, " a층의 b번째 숫자가 내려올 수 있는 곳은 a+1층의 b번째 숫자와, b+1번째의 숫자 밖에 없다" 라는 것을 의미한다.

7) 따라서, 삼각형의 1층에서 부터 N번째 층 까지 내려오면서, 6)의 식에만 맞게 계산을 해주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 501
using namespace std;
 
int N, Answer;
int Arr[MAX][MAX];
int DP[MAX][MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            cin >> Arr[i][j];
        }
    }
}
 
void Find_Max()
{
    int Max = 0;
    for (int i = 1; i <= N; i++)
    {
        if (DP[N][i] > Max) Max = DP[N][i];
    }
    Answer = Max;
}
 
void Solution()
{
    Arr[0][0] = Arr[0][1] = Arr[1][0] = DP[0][0] = DP[0][1] = DP[1][0] = 0;
    DP[1][1] = Arr[1][1];
    for (int i = 1; i < N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (DP[i + 1][j] < DP[i][j] + Arr[i + 1][j])
            {
                DP[i + 1][j] = DP[i][j] + Arr[i + 1][j];
            }
            if (DP[i + 1][j + 1] < DP[i][j] + Arr[i + 1][j + 1])
            {
                DP[i + 1][j + 1] = DP[i][j] + Arr[i + 1][j + 1];
            }
        }
    }
    Find_Max();
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}