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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

하나의 예시를 가지고 어떻게 접근해야 하는지 천천히 알아보자.

.

위와 같은 정수삼각형이 있다고 가정해보자.

그리고 지금부터 가장 윗층부터 아랫층부터 모든 숫자들을 탐색해보자. 탐색을 할 때에는, "해당 층수에서는 최댓값을 가지는 경우 그 값이 얼마인지?" 보다는 "해당 값을 선택했을 때, 가질 수 있는 최댓값"에 초점을 맞춰서 계산을 해보자.

가장 위층이 1층, 가장 아랫층이 3층 이라고 표현하겠다.

그럼 가장 먼저, 1층에 있는 숫자들을 한번 봐보자. 숫자는 '1' 1개뿐이다.

그럼 이 '1'을 밟았을 때, 가질 수 있는 최댓값은 얼마일까 ?? 당연히 '1'일 것이다. 그 윗층에는 층이 없기 때문이다.

[ 1층에 있는 '1'을 밟았을 때 얻을 수 있는 최댓값 = 1 ]

그럼 2층으로 넘어가보자.

2층에는 '2'와 '3'이라는 2개의 숫자가 있다.

그럼 이 '2'를 밟는 경우를 보자. 먼저, '2'를 밟을 수 있는 경로는 어떤 경로가 있을까 ??? 바로, 1층에서 '1'을 밟고, 2층에 있는 '2'를 밟는 경우가 있다. 그럼 그 경우 얻을 수 있는 최댓값은 '3'이 된다. 또 다른 경로가 존재하지 않기 때문에, 2층에 있는 '2'를 밟았을 때, 얻을 수 있는 최댓값은 '3'이 된다.

[ 2층에 있는 '2'를 밟았을 때 얻을 수 있는 최댓값 = 2 ]

그럼 '3'을 밟는 경우를 보자. '3'을 밟을 수 있는 경로는 어떤 경로가 있을까 ??? 바로, 1층에서 '1'을 밟고, 3층에 있는 '3'을 밟는 경우가 있다. 그럼 이 경우 얻을 수 있는 최댓값은 1 + 3 = '4' 가 된다. 또 다른 경로가 존재하지 않기 때문에, 2층에 있는 '3'을 밟았을 때, 얻을 수 있는 최댓값은 '4'가 된다.

[ 2층에 있는 '3'을 밟았을 때 얻을 수 있는 최댓값 = 3 ]

3층으로 넘어가보자.

3층에는 '4'와 '5'와 '6'이라는 3개의 숫자가 있다.

'4'를 밟는 경우를 보자. 먼저, '4'를 밟을 수 있는 경로는 ?? 바로, 1층에서 '1'을 밟고, 2층에서 '2'를 밟고, 3층에서 '4'를 밟는 경우가 있다. 다른 경우는 존재하지 않는다. 왜냐하면 2층에 있는 '3'이라는 값에서 3층에 있는 '4'로 오는 것은 문제의 조건에 위배되는 방식이기 때문에 적절한 경로가 되질 못한다. 그러므로, 이 외에 또 다른 경로는 존재하지 않는다. 따라서, 3층에 있는 '4'를 밟았을 때, 얻을 수 있는 최댓값은 1 + 2 + 4 = '7' 이 된다.

[ 3층에 있는 '4'를 밟았을 때 얻을 수 있는 최댓값 = 7 ]

'5'를 밟는 경우를 보자. 먼저, '5'를 밟을 수 있는 경로는 ?? 처음으로 지금까지와는 다르게 여러 경우가 존재한다.

1. 1층에서 '1' → 2층에서 '2' → 3층에서 '5' 를 밟는 경우

2. 1층에서 '1' → 2층에서 '3' → 3층에서 '5' 를 밟는 경우

이렇게 2가지 경우가 발생한다. 그럼 2가지 경우를 비교해보자.

첫 번째 경우는 1 + 2 + 5 = 8 이라는 결과를 가지게 되고 , 두 번째 경우는 1 + 3 + 5 = 9 라는 결과를 가지게 된다.

그럼 ! 이 때 얻을 수 있는 최댓값은 당연히 2개의 값 중 더 큰 값인 '9'가 될 것이다.

[ 3층에 있는 '5'를 밟았을 때 얻을 수 있는 최댓값 = 9 ]

'6'을 밟는 경우를 보자. 먼저, '6'을 밟을 수 있는 경로는 ?? 바로, 1층에서 '1'을 밟고, 2층에서 '3'을 밟고, 3층에서 '6'을 밟는 경우가 있다. 이 외에 다른 경로는 존재하지 않는다 ! 따라서 3층에 있는 '6'을 밟았을 때 얻을 수 있는 최댓값은 1 + 3 + 6 = 10 이 된다.

[ 3층에 있는 '6'을 밟았을 때 얻을 수 있는 최댓값 = 10 ]

그럼 위의 정수삼각형에서 얻을 수 있는 최댓값은 얼마일까 ?? 바로 , 3층에 있는 '6'을 밟았을 때 얻을 수 있는 10점이 최댓값이 된다. 지금부터는 위에서 색깔로 칠해진 말들을 다시 주목해보자.

본인이 위에서 설명을 하면서 정수삼각형들을 3가지로 나눠보았다. 그래서 위에서 보면 빨강색 , 파랑색 , 초록색 3가지 색깔이 존재하는 것이다.

가장 먼저 빨강색 글씨들은 "각 층에서, 가장 왼쪽에 있는 숫자들" 의 특징을 의미한다.

위의 설명에서 빨강색 글씨들만 다시 한번 읽어보자. 그럼 빨강색 경우를 보면 다음과 같은 숫자들만 빨강색으로 표시가 되어있다.

.

그리고 빨강색 설명에는 뒤에 꼭 "이 외에 다른 경로는 존재하지 않는다" 라는 설명이 덧붙여져 있었다. 이게 ! 각 층에서, 가장 왼쪽에 있는 숫자들의 특징이다. 정리해서 이야기해보면, "각 층에서, 가장 왼쪽에 있는 숫자를 밟았을 때, 얻을 수 있는 최댓값은, 그 이전층에서 가장 왼쪽에 있는 숫자를 밟았을 때 얻을 수 있는 최댓값에만 영향을 미친다" 는 것이다.

위의 설명을 보면, 2층에 있는 '2'와 , 4층에 있는 '4' 모두 밟을 수 있는 경로가 하나씩만 존재한다고 되어있다. 그리고 그 경로들의 특징을 보면, 이전층의 가장 왼쪽에 있는 숫자에만 영향을 받는다는 것이다.

두 번째로 파랑색 글씨들은 "각 층에서, 가장 오른쪽에 있는 숫자들" 의 특징을 의미한다.

바로 위와 같은 숫자들이다. 이 경우에는 빨강색 글씨와는 반대로, 가장 오른쪽에 있는 숫자들에만 영향을 미치게 된다.

파랑색 설명에도 마찬가지로, "이 외에 다른 경로는 존재하지 않는다" 라는 설명이 덧붙여져 있었다. 이게 ! 각 층에서, 가장 오른쪽에 있는 숫자들의 특징이다. 정리해서 이야기해보면, "각 층에서, 가장 오른쪽에 있는 숫자를 밟았을 때, 얻을 수 있는 최댓값은, 그 이전층에서 가장 오른쪽에 있는 숫자를 밟았을 때 얻을 수 있는 최댓값에만 영향을 미친다." 는 것이다.

위의 설명을 보면, 2층에 있는 '3'과, 3층에 있는 '6' 모두 밟을 수 있는 경로가 하나씩만 존재한다고 되어있다. 그리고 그 경로들의 특징을 보면, 이전층의 가장 오른쪽에 있는 숫자에만 영향을 받는다는 것이다.

마지막으로 초록색 글씨들은 "각 층에서, 가장 왼쪽도, 가장 오른쪽도 아닌 숫자들"의 특징을 의미한다.

.

바로 위의 그림에서 '5' 같은 숫자들이다. 빨강색, 파랑색에 있었던 숫자들과는 다르게 2가지 경로가 존재한다.

바로, 현재 위치의 왼쪽 위에서 내려오는 경우와 오른쪽 위에서 내려오는 경우가 존재하고 , 이 값들을 비교해서 최댓값을 갱신해 주어야 하는 놈들이다.

위의 설명을 보면, 3층에 있는 '5'는 2가지 경로가 존재했었고, 그 2가지 경로에서 얻을 수 있는 값들을 비교해서 최댓값을 찾았었다.

그럼 ! 위의 내용을 일반화된 식으로 표현을 해보자.

간단하게 정수삼각형을 2차원 배열로 나타내보자.

Triangle[a][b] = c 이런식으로 ! Triangle[a][b] = c 의 의미는 "a층에 있는 b번째 숫자는 c입니다" 를 의미한다.

위의 정수삼각형을 이 2차원 배열로 표현해보면

Triangle[1][1] = 1

Triangle[2][1] = 2 , Triangle[2][2] = 3

Triangle[3][1] = 4 , Triangle[3][2] = 5 , Triangle[3][3] = 6

이렇게 표현할 수 있다.

그리고 각 숫자들을 선택했을 때, 얻을 수 있는 최댓값을 DP[][] 라는 2차원 배열로 표현해보자

DP[a][b] = c 이런식으로 ! DP[a][b] = c 의 의미는 "a층에 있는 b번째 숫자를 밟았을 때, 얻을 수 있는 최댓값은 c입니다" 를 의미한다.

그리고 위의 배열 2개(Triangle, DP) 를 이용해서 빨강색 / 파랑색 / 초록색 숫자들의 값들을 계산해보자.

가장 먼저, DP[1][1] 의 값은 '1'일 것이다. 왜냐하면 1층에 있는 첫 번째 숫자는 그 자체가 최댓값이기 때문에 '1'이 될 것이다. 그럼 DP[2][1] 의 값은 얼마일까 ?? DP[2][1]은 2층에 있는 첫 번째 숫자를 의미하고 , 빨강색으로 표시된 숫자 '2'를 의미한다. 이 경우에는 이전 층의 가장 왼쪽에 있는 숫자에 영향을 미친다고 했다. 즉 ! DP[1][1] + Triangle[2][1] 이 된다.

그럼 DP[3][1]의 값은 ?? DP[3][1]은 3층에 있는 첫 번째 숫자를 의미하고 , 빨강색으로 표시된 숫자 '4'를 의미한다.

이 경우에는 DP[2][1] + Triangle[3][1] 이 된다. 그럼 DP[N][1]의 값은 얼마가 될까 ??

바로 ! DP[N][1] = DP[N - 1][1] + Triangel[N][1]이 된다. 이게 빨강색 숫자들의 일반화된 점화식이다.

그럼 파랑색 숫자들을 표현해보자.

DP[2][2] 의 값은 얼마일까 ?? DP[2][2]는 2층에 있는 두 번째 숫자로써, 파랑색으로 표시된 숫자'3'을 의미한다.

이 경우에는 이전 층의 가장 오른쪽에 있는 숫자에만 영향을 미치게 된다. 즉 ! DP[2][2] = DP[1][1] + Triangle[2][2] 가 된다. DP[3][3]은 ?? DP[3][3] = DP[2][2] + Triangle[3][3] 이 된다.

그럼 DP[N][N]의 값은 얼마가 될까 ?? 바로 ! DP[N][N] = DP[N - 1][N - 1] + Triangle[N][N] 이 된다.

그럼 초록색 숫자들을 표현해보자.

DP[3][2] 의 값을 계산해보자. DP[3][2]는 3층에 있는 두 번째 숫자를 밟았을 때, 얻을 수 있는 최댓값을 구해야 하기 때문에 2가지 경우를 생각해주어야 한다. 바로 , DP[2][1] (2층에 있는 첫 번째 숫자를 밟았을 때 얻을 수 있는 최댓값) 과 DP[2][2] (2층에 있는 2번째 숫자를 밟았을 때 얻을 수 있는 최댓값) 을 비교해 주어야 한다.

즉 ! DP[3][2] = Max(DP[2][1] , DP[2][2]) + Triangle[3][2] 가 된다.

그럼 DP[N][A] 의 값은 얼마가 될까 ?? 여기서 'A'는 가장 왼쪽도 가장 오른쪽도 아닌 가운데에 있는 숫자들, 즉, 초록색 숫자를 의미한다고 가정하자. 그럼 DP[N][A]의 값은 얼마가 될까 ??

바로 ! DP[N][A] = Max(DP[N - 1][A - 1] + DP[N - 1][A]) + Triangle[N][A] 가 된다.

마지막으로 정리해보면 , 각 층에 있는 숫자들을 3가지 그룹으로 나눌 수 있는데, 각 그룹은 그들만의 특징을 가지고 있다.

따라서, 현재 탐색하고자 하는 숫자가 3가지 그룹 중, 어느 그룹에 속하는 그룹인지 판단 후, 위에서 도출해낸 점화식을 통해서 계산을 해주면 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 510
using namespace std;
 
int N;
int Triangle[MAX][MAX];
int DP[MAX][MAX];
 
int Max(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 >> Triangle[i][j];
        }
    }
}
 
void Solution()
{
    DP[1][1] = Triangle[1][1];
    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1) DP[i][j] = DP[i - 1][j] + Triangle[i][j];
            else if (j == i) DP[i][j] = DP[i - 1][j - 1] + Triangle[i][j];
            else DP[i][j] = Max(DP[i - 1][j - 1] + Triangle[i][j], DP[i - 1][j] + Triangle[i][j]);
        }
    }
    int Answer = 0;
    for (int i = 1; i <= N; i++) Answer = Max(Answer, DP[N][i]);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}