문제

1
2
3
4
5
    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
3
4
5
6
7
8
9
10
예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1
30

풀이

처음에는 탑 다운 방식으로 7을 선택하고 3과 8을 더한 수는 DP[2][0], DP[2][1]에 저장하는 방법으로 진행해보려고 하였다.

그런데 횟수가 많아지고 DP[3][1]에서 DP[2][0]과 DP[2][1] 중 큰 값을 구해서 더해야하는데 만약 3이 아니라 10이라면 1과 10을 제외한 2~9를 반복문을 돌면서 그 중에 최댓값인 것과 더해서 DP 값을 구해야 하기에 이는 너무 복잡하여 다르게 생각해보려고 노력했지만 한 문제에 너무 많은 시간을 쏟는 것 같아 다른 사람의 해설을 참고하였다.

위에서 부터 순서대로 7-3-8-7-5를 선택하여 총합 30이라는 숫자를 출력하였는데, 이는 반대로 생각해볼 수 있다.

맨 아래에서부터 시작하여 4, 5, 2, 6, 5의 바로 위의 숫자에는 4개의 숫자가 있다. 즉, 5번째 줄의 숫자를 2개씩 짝지어서 비교하여 큰 값을 바로 위에 숫자와 더하여 누적하면서 위로 올라가다보면 최종적으로 맨 위에는 최댓값이 남게되는 방식이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const n = +input.shift();
const triangle = input.map((floor) => floor.split(" ").map(Number));

const solution = (n, triangle) => {
  if (n === 1) return triangle[0][0];
  if (n === 2) return triangle[0][0] + Math.max(...triangle[1]);
  for (let i = n - 2; i >= 0; i--) {
    triangle[i].forEach((v, idx, self) => {
      self[idx] = v + Math.max(triangle[i + 1][idx], triangle[i + 1][idx + 1]);
    });
  }
  return triangle[0][0];
};

console.log(solution(n, triangle));
  • DP 배열을 만들지 않고 triangle 배열을 그대로 바꾸어 반환하였다.

참고