[백준] JavaScript - 정수 삼각형 (1932)

개요

문제 이름: 정수 삼각형 (1932)
문제 링크: https://www.acmicpc.net/problem/1932
플랫폼: 백준
알고리즘 분류: 다이나믹 프로그래밍
소요 시간: 1시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 정수 삼각형에서 맨 위층부터 아래층까지 경로를 따라 내려오면서 수를 선택할 때, 선택된 수의 합이 최대가 되는 경로를 구하는 문제입니다.

 

이를 해결하기 위해 다이나믹 프로그래밍(DP) 알고리즘을 활용합니다. 다이나믹 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 푸는 알고리즘으로, 이전에 계산한 부분 문제의 답을 메모리에 저장하여 다시 계산하지 않도록 합니다.

 

이 문제에서는 특정 층의 특정 위치에 도달했을 때 해당 위치까지의 선택된 수의 합이 최대인 값을 메모이제이션(Memoization)하며 문제를 해결합니다. 맨 위층부터 시작하여 한 층씩 내려오면서, 각 위치에 대해 이전 층의 대각선 왼쪽과 대각선 오른쪽 위치 중 더 큰 값을 선택하여 현재 위치의 값에 더합니다. 이렇게 최하층까지 내려왔을 때, 최하층의 값들 중 최대값이 선택된 수의 최대 합이 됩니다.

 

문제를 정리하면 다음과 같습니다.

• 크기가 n인 정수 삼각형이 주어집니다.
• 맨 위층 (0, 0) 위치부터 시작하여 아래층으로 내려옵니다.
• 다음 층으로 내려올 때는 현재 층의 대각선 왼쪽 또는 오른쪽 숫자 중 하나를 선택하여 내려옵니다.
• 이렇게 선택된 수의 합이 최대가 되도록 하는 경로를 찾고, 그 합을 출력해야 합니다.

문제의 핵심은 특정 층과 위치에 도달했을 때의 최대합을 기록해두는 DP 테이블을 만드는 것입니다. 식을 세워보면 다음과 같습니다.

• dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] (i > 0, 0 < j < i)
• dp[i][0] = dp[i-1][0] + triangle[i][0] (i > 0, j = 0)
• dp[i][i] = dp[i-1][i-1] + triangle[i][i] (i > 0, j = i)

즉, 현재 층의 각 위치에서는 이전 층의 대각선 왼쪽 또는 오른쪽 위치 중 최대값을 선택하여 현재 위치의 값과 더합니다. 맨 왼쪽(j=0)과 맨 오른쪽(j=i)에서는 대각선 한 쪽에서만 값을 선택합니다.

 

이렇게 맨 위층부터 최하층까지 계산하면 DP 테이블에는 각 위치까지의 최대합이 저장되고, 최하층에 저장된 값들 중 최대값이 정답이 됩니다.

 

코드의 흐름은 다음과 같습니다.

1. 삼각형의 크기 n을 입력받습니다.
2. 정수 삼각형을 입력받아 2차원 배열 triangle에 저장합니다.
3. DP 테이블(dp)을 n x n 크기로 초기화합니다.
4. dp[0][0]에 triangle[0][0]의 값을 저장합니다. (맨 위층)
5. 두번째 층부터 최하층까지 DP 테이블을 채워나갑니다.
   • 맨 왼쪽(j=0)과 맨 오른쪽(j=i)는 한 쪽에서만 선택합니다.
   • 나머지 위치는 이전 층의 대각선 왼쪽과 오른쪽 중 최대값을 선택하여 더합니다.
6. 최하층에 있는 값들 중 최대값을 출력합니다.

 

시도

1차 시도  (성공)

// 대충 데이터 받기
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = parseInt(input[0]);

// 삼각형 데이터를 2차원 배열로 변환 (각 줄을 공백으로 분리하고 숫자로 변환)
const triangle = input.slice(1).map(row => row.split(' ').map(Number));

// DP 테이블 초기화 (n x n 크기의 2차원 배열) (0으로 초기화)
const dp = Array.from({ length: n }, () => Array(n).fill(0));

// DP 테이블의 첫 번째 값은 삼각형의 꼭대기 값으로 설정
dp[0][0] = triangle[0][0];

// 각 층별로 순회
for (let i = 1; i < n; i++) {
    // 현재 층의 각 위치별로 순회
    for (let j = 0; j <= i; j++) {
        // 현재 위치가 왼쪽 끝인 경우
        // 바로 위의 값에서만 내려올 수 있음
        if (j === 0) {
            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] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
        }
    }
}

// 마지막 층에서 가장 큰 값을 찾아 출력
console.log(Math.max(...dp[n-1]));

이 문제는 DP를 활용해 각 위치에 도달하기까지의 최대합을 메모이제이션하면서 문제를 해결합니다.

1. fs 모듈을 사용하여 입력을 읽어옵니다. 입력은 개행문자('\n')로 구분된 여러 줄로 이루어져 있습니다.
2. 첫째 줄에서 삼각형의 크기 n을 파싱하여 정수로 저장합니다.
3. 둘째 줄부터 n+1번째 줄까지의 입력을 공백(' ')으로 분리하고 숫자로 변환하여 2차원 배열 triangle에 저장합니다.
4. DP 테이블 dp를 n x n 크기로 생성하고 0으로 초기화합니다.
   1. Array.from()과 fill() 메서드를 사용하여 초기화합니다.
5. dp[0][0]에 triangle[0][0]의 값을 저장합니다. (맨 위층의 값)
6. 두번째 층(i=1)부터 최하층(i=n-1)까지 반복합니다.
   1. 각 층(i)에서 왼쪽부터 오른쪽까지 위치(j)를 반복합니다.
   2. 맨 왼쪽(j=0)에서는 dp[i][j] = dp[i-1][j] + triangle[i][j]로 계산합니다.
   3. 맨 오른쪽(j=i)에서는 dp[i][j] = dp[i-1][j-1] + triangle[i][j]로 계산합니다.
   4. 그 외의 위치에서는 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]로 계산합니다. 즉, 이전 층의 대각선 왼쪽과 오른쪽 중 최대값을 선택하여 현재 위치의 값에 더합니다.
7. 최하층의 값들(dp[n-1])을 spread 연산자(...)로 펼쳐서 Math.max()의 인자로 전달하여 최대값을 구합니다.
8. 마지막으로 그 값을 출력합니다.

 

사용된 주요 메서드

• Array.from(): 유사 배열 객체(array-like object)나 반복 가능한 객체(iterable)로부터 새로운 Array 인스턴스를 생성합니다.
• Array.prototype.fill(): 배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채웁니다.
• Array.prototype.slice(): 배열의 begin부터 end까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다. 원본 배열은 바뀌지 않습니다.
• Array.prototype.map(): 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.
• Math.max(): 주어진 숫자들 중 가장 큰 숫자를 반환합니다.

 

시간복잡도와 공간복잡도

• 시간복잡도: O(n^2)
  • 삼각형의 크기가 n이므로 DP 테이블을 채우는 데 필요한 반복문의 총 횟수는 약 n^2/2번입니다. 따라서 O(n^2)의 시간 복잡도를 가집니다.
• 공간복잡도: O(n^2)
  • 입력으로 주어진 삼각형을 저장하는 triangle 배열과 DP 테이블인 dp 배열이 각각 n x n 크기의 공간을 차지합니다. 따라서 O(n^2)의 공간 복잡도를 가집니다.

 

사족

이 문제는 삼각형의 크기에 따라 시간과 공간이 제곱으로 증가하므로, n이 매우 큰 경우에는 시간 초과나 메모리 초과가 발생할 수 있습니다. 그러나 이 문제에서 주어진 제한 조건(1 <= n <= 500) 내에서는 통과할 수 있습니다.