BOJ1932

BaekJoon 1932 : 정수 삼각형

문제

        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>

int main() {

    int size;               // 1 <= size <= 500
    std::cin >> size;
    int numOfElements = size * (size + 1) / 2;

    // 원소들을 저장할 배열, 누적 합을 저장할 배열
    int triangle[numOfElements], sums[numOfElements] = {0};
    
    // 삼각형 입력받기
    for (int i = 0; i < numOfElements; i++)
    {
        std::cin >> triangle[i];
    }
    
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            // i + j의 왼쪽 위 숫자의 인덱스는?     
            // i + j의 오른쪽 위 숫자의 인덱스는?   

             int leftUpper, rightUpper;
            if(j == 0)
                leftUpper = 0;
            else
                leftUpper = sums[(i - 1) * i / 2 + (j - 1)];

            if(j == i)
                rightUpper = 0;
            else
                rightUpper = sums[(i - 1) * i / 2 + j];

            sums[i * (i + 1) / 2 + j] = triangle[i * (i + 1) / 2 + j] + std::max(leftUpper, rightUpper);
        }
        
    }
    
    // sums 배열의 가장 아래층에 모인 합들 중 최대를 고른다.
    int max = sums[numOfElements - 1];

    for (int i = 1; i <= size; i++)
    {
        if(max < sums[numOfElements - i])
            max = sums[numOfElements - i];
    }

    std::cout << max << std::endl;

}

큰 문제없이 풀어낼 수 있었다.

입력받은 원소들을 담는 배열과 동일한 크기의 배열을 하나 더 만들고 거기에 누적합을 담아,

순차적으로 내려오다보면 문제가 풀리도록 풀었다.

원소의 왼쪽 위, 그리고 오른쪽 위에 위치할 원소의 인덱스를 잡는 부분에서 살짝 헤메었는데,

배열에 Complete Binary Tree를 저장할 때, 부모와 자식의 관계에서 힌트를 얻어 풀었다.

처음에는 배열을 위주로 활용하여 풀었는데, 두번째에는 동적인 배열을 활용해 풀어보았다.

두번째 답

#include <iostream>
#include <vector>
#include <algorithm>

int main() {

    int size;               // 1 <= size <= 500
    std::cin >> size;

    // 원소들을 저장할 배열, 누적 합을 저장할 배열
    std::vector<std::vector<int>> triangle(size);
    std::vector<std::vector<int>> sums(size);

    // 삼각형 입력받기
    for (int i = 0; i < size; i++)
    {
        triangle[i].resize(i + 1);
        sums[i].resize(i + 1);
        for (int j = 0; j <= i; j++)
        {
            std::cin >> triangle[i][j];
        }
        
    }
    
    // 삼각형의 모든 원소들을 순회하면서 최대 합 계산
    sums[0][0] = triangle[0][0];
    for (int i = 1; i < size; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            int leftUpper = (j == 0) ? 0 : sums[i - 1][j - 1];
            int rightUpper = (j == i) ? 0 : sums[i - 1][j];
            sums[i][j] = triangle[i][j] + std::max(leftUpper, rightUpper);
        }
    }
    
    // 가장 아래층에 모인 합들 중 최대를 고른다.
    int max = *std::max_element(sums[size - 1].begin(), sums[size - 1].end());

    std::cout << max << std::endl;
}

algorithm은 *std::max_element 함수를 쓸려고 불러내었다.

확실히 이렇게 하니, 삼각형의 층을 의미하는 i와 한 층 내에서의 순번을 의미하는 j가 더욱 직관적으로 보인다.

가독성은 확실히 이 버전이 더 좋은 것 같다.

각각의 버전으로 풀었을 때, 배열을 사용해 푼 버전이 조금 더 빠르고, 메모리를 덜 사용했다.

아무래도 벡터를 사용한 것과, 그렇지 않을때의 차이가 이렇게 나타나는 것 같다.