[node.js,백준]1932 - 정수 삼각형

목차

 

 

 문제

링크

https://www.acmicpc.net/problem/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번째 줄까지 정수 삼각형이 주어진다.

 

출력

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

 

주저리

삼각형의 길이가 1일꺼란 생각을하지않아서 2이상으로 짠 거에서

1에 대한 예외처리를 추가한 방식으로 하였다.

 

음수가 없으니 결과값은 제일 마지막 arrs에 배열로 담겨있을 것이고

마지막 행의 결과값들은 이전값의 왼쪽과 오른쪽을 통해서만 값을 받을수 있는데

각각 제일 왼쪽과 오른쪽은 이전에섭다을수있는 값이 하나이므로 그값을 더해주고

나머지 케이스들은 왼쪽과 오른쪽의 Max값으로 해결하였다.

그리고 마지막 행의 배열에 최대값을 가져와주면 해결 된다.

 

풀이

• 정수 삼각형 문제는 동적 프로그래밍(Dynamic Programming)을 활용하여 각 행의 최대 합을 찾는 문제입니다. 주어진 삼각형에서 맨 위부터 시작하여 아래로 내려갈 때, 각 위치에서 선택할 수 있는 숫자 중 최대 합을 구하는 것이 목표입니다.

 입력 처리

• 문제에서 주어진 삼각형의 수들은 입력으로 받으며, 이는 보통 여러 줄에 걸쳐 제공됩니다. 각 줄의 숫자들은 삼각형의 한 행을 구성합니다.

 동적 프로그래밍 배열 초기화

• 문제 해결을 위해 각 행의 최대합을 저장할 배열을 초기화합니다. 이 배열은 삼각형의 맨 위부터 각 위치까지의 최대 합을 계속 갱신하며 저장합니다.

 점화식 설정

• - 삼각형의 각 위치에서 선택할 수 있는 최대 값은 이전 행까지의 계산에서 유도됩니다.
• - 맨 왼쪽 위치는 바로 위의 값과 현재 값을 더합니다.
• - 맨 오른쪽 위치는 위의 오른쪽 대각선 값과 현재 값을 더합니다.
• - 중간 위치는 위의 왼쪽 대각선 값과 오른쪽 대각선 값 중 더 큰 값을 현재 값과 더합니다.

 최대값 계산

• 삼각형의 가장 하단 행까지 계산을 마친 후, 가장 마지막 행에 저장된 값들 중 가장 큰 값이 문제의 최종 답이 됩니다.

 

 코드

// 정수 삼각형
var fs = require('fs');
// var input = fs.readFileSync('/dev/stdin').toString();
let input = `1
7`

let real = input.trim().split("\n");
let arrs = [0];

function testF(N, rest) {
    for (let i = arrs.length; i <= N; i++) {
        arrs.push([]);
        let row = rest[i - 1];
        for (let j = 0; j < row.length; j++) {
            if (j === 0) {
                arrs[i][j] = arrs[i - 1][j];
            }
            else if (j === row.length - 1) {
                arrs[i][j] = arrs[i - 1][j - 1];
            }
            else {
                arrs[i][j] = Math.max(arrs[i - 1][j - 1], arrs[i - 1][j]);
            }
            arrs[i][j] = arrs[i][j] + rest[i - 1][j]
        }
    }
}

function solution(real) {
    let [T, ...rest] = real;
    rest = rest.map((row) => {
        let a = row.split(" ").map(Number);
        return a
    });
    if (rest.length === 1) {
        console.log(rest[0][0])
        return;
    }
    arrs.push(rest[0][0]);
    arrs.push([rest[0][0] + rest[1][0], rest[0][0] + rest[1][1]])
    // console.log({ rest });
    testF(Number(T), rest)
    // console.log({ arrs })
    console.log(Math.max(...arrs[T]));
}
solution(real);