백준 No.1932 [정수 삼각형]

// Baekjoon Online Judge No.1932 [정수 삼각형]

---

   Code   

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<vector<int>> tri;
vector<int> ground;
 
int main() {
    int N;
    cin >> N;
 
    tri.assign(N + 1, vector<int>(N + 1, -1));
    ground.assign(N + 1, 0);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> tri[i][j];
        }
    }
 
    ground[1] += tri[1][1];
 
    for (int i = 2; i <= N; i++) {
        vector<int> temp(ground);
 
        for (int j = 1; j <= i; j++) {
            if (j != 1 && j != i) {
                temp[j] = tri[i][j] + max(ground[j - 1], ground[j]);
            }
            else if (j == 1) {
                temp[j] = ground[j] + tri[i][j];
            }
            else if (j == i) {
                temp[j] = ground[j - 1] + tri[i][j];
            }
        }
        ground = temp;
    }
 
    sort(ground.begin(), ground.end());
 
    cout << ground[N];
    return 0;
}

---

   How to solve   

   vector<vector<int>> tri;  는 정수 삼각형이 입력될 벡터이다. 벡터 어레이의 첫 시작 index는 0이므로, 1부터 N까지 사용하기 위해  tri.assign(N + 1, vector<int>(N + 1, -1));  와 같이 N + 1개의 공간(층)을 확보한 것을 볼 수 있다. 또한 편의를 위해 맨 윗층을 N층이 아닌 1층이라고 생각하고 풀었으며 앞으로의 설명에서도 맨 윗층을 1층, 맨 아랫층을 N층으로 두고 설명할 것이다.

 

  또한 tri 벡터의 각 행에 대한 열의 size는 1층은 1개, 2층은 2개 ... N층은 N개 이런식으로 가야하지만 그렇게 큰 메모리가 할당되지 않을 것 이므로 그냥 모든 행에 N + 1개의 size를 주었다. 이 역시 N이 아닌 N + 1을 준 이유는 tri 벡터의 각 행에 해당하는 열들의 시작 index 또한 1부터 시작하기 위해서이다!

 

N이 4일때의 tri 벡터 예시

   vector<int> ground;  는 1층부터 N층까지 가면서, 그때그때 ground[k]의 k번째 항에 입력될 수 있는 가장 큰 값이 입력된다. 42번 line에서 sorting이 되기 전 ground벡터의 상태는

 

• ground[1] == 1번째 항에 올 수 있는 최댓값
• ground[2] == 2번째 항에 올 수 있는 최댓값
• ground[k] == k번째 항에 올 수 있는 최댓값
• ground[N] == N번째 항에 올 수 있는 최댓값

가 된다. ground 벡터는 각 층마다 최대값이 저장되어있는 벡터가 아니다!!! 결국 구할것은 N층까지 간 후 ground에 들어있는 값들 중 가장 큰 값이므로 ground벡터는 계속해서 바뀌면서 한층한층 건너오면서 그 층마다 존재하는 index들에 해당하는 항이 가질 수 있는 최대값을 저장한 것이다.

 

  우선 1층에 입력될 숫자 한개는 앞으로 <Dynamic Programming (동적 계획)>을 사용하기 위한 초기값이 될 것 이므로 25번째 line 전에 미리 ground[1]에 입력을 시켜주어야 한다.

 

N이 4일때의 ground 벡터 예시

  층이 바뀔때마다 ground 벡터 원소의 값들도 바뀐다. 맨 윗층 ground[1] 에는 앞서 말 했듯 tri[1][1]값을 넣었다. 그럼 2번째 층에서 ground[1]의 값과 ground[2]의 값이 어떻게 될지 생각해보자. 결론부터 말 하자면

 

• 2번째 층에서의 ground[1] = 1번째 층에서의 ground[1] + tri[2][1]
• 2번째 층에서의 ground[2] = 1번째 층에서의 ground[1] + tri[2][2]

가 된다. 3번째 층부터는 2번째 층과는 좀 다른게 보일 것이다. 3번째 층에서의 ground[2]는 2번째 층에서의 ground[1], ground[2] 중 값을 골라서 더해야하기 때문이다. 우리는 최대값을 구하는게 목적이므로 둘 중 더 큰 값을 더하면 될것이라고 생각할 수 있다.

 

• 3번째 층에서의 ground[2] = 2번째 층에서의 ground[1], ground[2] 값중 큰 값 + tri[3][2]

아래 그림을 참고해보자.

 

코드화된 각 층, 열에 해당하는 ground 값

 

  이를 일반화한 코드가 위 코드의 25번째 ~ 40번째 line이다. 그런데 이 반복문 안에서  vector<int> temp(ground);  가 있는 이유는 무엇일까? 그 이유는 간단하게 알 수 있다. 위 그림의 두 번째 층에 ground[2]를 보면 ground[1]의 값이 연산에 포함되는것을 알 수 있다. 이 ground[1]은 첫 번째 층의 ground[1]를 의미한다. 하지만 2번째 층의 ground[2]값을 정의하기 이전 2번째 층의 ground[1]의 값이 정의되면서 2번째 층의 ground[2]의 값에 의도하고자 하는 ground[1]의 값이 들어가지 않음을 알 수 있다. 이에 대한 해결책으로, 각 층에 대한 연산을 시작하기 전 ground벡터와 똑같은 temp벡터를 생성하였다. 계산을 하는 도중에는 temp벡터의 원소값이 변경이 되고 ground벡터의 원소값은 마치 상수와 같이 사용된다. 그리고 그 층에대한 연산이 전부 끝난 후 ground벡터에 temp벡터를 복사한다.

 

  이렇게 ground벡터의 값을 다 정의한 후 42번째 line과 같이 오름차순으로 sorting을 한다. 오름차순으로 정렬이 되었으므로 ground벡터의 가장 마지막 값인 ground[N]가 우리가 구하고자 하는 값이 됨을 알 수 있다.