[01932] 정수 삼각형

Byeongmin·2021년 8월 21일

백준 단계별로 풀어보기

목록 보기

46/69

[01932] 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

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

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

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

입력

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

출력

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

코드

#include <iostream>
#include <vector>

using namespace std;

/* 조건 */

/* 변수 */
int n, tmp;
vector<int> v;

/* 함수 */

int main() {
    /* 입력 */
    cin >> n;
    for(int i = 0; i < n*(n+1)/2; i++) {
        cin >> tmp;
        v.push_back(tmp);
    }

    /* 풀이 */
    for(int i = n-1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            v[i*(i-1)/2 + j] += max(v[i*(i+1)/2 + j], v[i*(i+1)/2 + j + 1]);
        }
    }

    /* 출력 */
    cout << v[0];
}

풀이과정

이번 문제는 이전에 풀었던 [01149] RGB거리 문제와 비슷하게 앞의 선택지에 따라 뒤에 선택할 수 없는 선택지가 생기므로 모든 지점에서 최선의 경우를 저장하며 따져봐야 한다.

논리

우선 이 문제를 해결하는 방법은 n-1층부터 시작해 위로 올라가면서 아래의 근접한 두 숫자들 중 큰 숫자를 더해 다시 저장하면 마지막 1층에 저장된 값이 최댓값이다.
예시로 직접 살펴보자.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위는 n = 5인 경우이다.
n = 4부터 시작해 각 숫자의 아래 두 수들 중 큰 값을 골라 더해준다.

        7
      3   8
    8   1   0
  7  12  10   10

이렇게 되면 각 더한 숫자쪽의 경로를 택했을 때의 숫자가 되며, 이는 각 지점에서 갈 수 있는 경로의 최댓값이다.
한번 더 반복해보면

        7
      3   8
    20  13  10

위와 같이 된다.
이 역시 각 지점에서 갈 수 있는 최댓값의 경로를 선택한 경우이다.
이를 반복하다보면 결국 1층에 최댓값이 저장될 것이다.

index

위의 삼각형에 index를 넣어보면 아래와 같이 된다.

각 층의 index는 0, 1, 3, 6, 10, 15, ... 으로 계차가 등차수열(1, 2, 3, 4, 5, ...)인 계차수열이다.
이 index들을 일반항으로 구하면 n층의 첫번째 index는 n * (n - 1) 이다.

풀이

모든 준비가 끝났다.
vector에 모든 입력을 받고,

/* 입력 */
cin >> n;
for(int i = 0; i < n*(n+1)/2; i++) {
    cin >> tmp;
    v.push_back(tmp);
}

index값을 이용해 다음과 같은 반복문으로 뒤에서부터 올라오면서 최댓값을 더해 1층까지 올라온다.

/* 풀이 */
for(int i = n-1; i > 0; i--) {
    for(int j = 0; j < i; j++) {
    	// n층의 j번째 숫자 += n+1층의 j번째, j+1번째 숫자들 중 큰 숫자
        v[i*(i-1)/2 + j] += max(v[i*(i+1)/2 + j], v[i*(i+1)/2 + j + 1]);
    }
}