[백준 1932번 정수 삼각형 - node.js] [알고리즘 기초 1/2]

https://www.acmicpc.net/problem/1932

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번째 줄까지 정수 삼각형이 주어진다.

 

출력

 

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

 

예제 입출력

 

입력	출력
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30

 

풀이[node.js]

 

 

728x90

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(inputs[0]);
inputs.shift();
var dp = [[Number(inputs[0])],
[Number(inputs[1].split(' ')[0]) + Number(inputs[0]), Number(inputs[1].split(' ')[1]) + Number(inputs[0])]];
for(var i=2; i<cases; i++){
    var arr = inputs[i].split(' ').map(v=>Number(v));
    var tmp = [];
     for(var j=0; j<arr.length; j++){
         if(j===0){
             tmp.push(dp[i-1][0] + arr[j]);
         }else if(j===arr.length-1){
             tmp.push(dp[i-1][arr.length-2] + arr[j]);
         }else{
             tmp.push(Math.max(dp[i-1][j], dp[i-1][j-1]) + arr[j]);
         }
    }
    dp.push(tmp);
}
console.log(Math.max(...dp[cases-1]));