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번째 줄까지 정수 삼각형이 주어진다.
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
30
✅ 답안 #1
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const n = Number(input.shift());
const dp = input.map((v) => v.split(' ').map(Number));
// 각 칸에 도달할 때까지의 최대값을 계산하여 dp 배열 채우기
for (let i = 1; i < n; i++) {
for (let j = 0; j <= i; j++) {
let max; // 이전 값들(왼쪽 위 혹은 오른쪽 위) 중 최대값을 저장할 변수
// 맨 왼쪽(j=0) 위에서 오는 경우
if (j === 0) max = dp[i - 1][j];
// 맨 오른쪽(j=i) 위에서 오는 경우
else if (j === i) max = dp[i - 1][j - 1];
// 왼쪽 위 또는 오른쪽 위 중 최대값 선택
else max = Math.max(dp[i - 1][j], dp[i - 1][j - 1]);
dp[i][j] += max;
}
}
console.log(Math.max(...dp[n - 1]));
✅ 답안 #2
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const n = Number(input.shift());
const arr = input.map((v) => v.split(' ').map(Number));
function solution(n, arr) {
// 삼각형 크기(n)이 1 일 때
if (n === 1) return arr[0][0];
// 삼각형 크기(n)이 2 일 때
else if (n === 2) return arr[0][0] + Math.max(...arr[1]);
// 삼각형 크기(n)이 3 이상 일 때
for (let i = n - 2; i >= 0; i--) {
for (let j = 0; j < arr[i].length; j++) {
arr[i][j] += Math.max(arr[i + 1][j], arr[i + 1][j + 1]);
}
}
console.log(arr);
return arr[0][0];
}
console.log(solution(n, arr));