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

출력

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

풀이

const triangle = () => {
  const [[n], ...arr] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((v) => v.split(" ").map(Number));
  let dp = Array.from({ length: n }, (v, i) =>
    Array.from({ length: i + 1 }, (v) => 0)
  );
  dp[0][0] = arr[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] + arr[i][j];
      else if (j === i) dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
      else dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
    }
  }
  console.log(Math.max(...dp[n - 1]));
};

triangle();

반성회

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5 // arr 배열

            7
         10   15
       18  16   15
    20   25   20   19
24   30   27   26   19 // dp 배열

• dp 배열에는 각 칸마다 지금까지 더한 수들의 최대값을 저장한다
• 예를 들어, dp[3][1] 의 경우 지금까지의 최대값이 7 + 3 + 8 이므로 여기에 arr[3][1] 을 더한 값인 25가 저장되게 된다

1. 삼각형의 모양과 똑같이 생긴 배열 dp를 만든다, dp의 각 칸과 입력값 (arr) 의 각 칸은 대응한다
2. dp의 0번째 행은 이전 행이 존재하지 않기 때문에 지금까지의 합은 arr[0][0]이 들어간다
3. dp의 1번째 행부터 이전 행을 이용해서 각 위치 ([i][j]) 별 누적 합의 최대값을 저장한다
   • dp[i][j] 는 dp[i - 1][j]와 dp[i - 1][j - 1] 중 더 큰 값에 arr[i][j] 를 더한 값이다
   • j가 0일 경우, dp[i][j] 는 삼각형의 왼쪽 끝에 위치하므로 dp[i - 1][j - 1]이 존재하지 않는다 ⇒ 따라서 dp[i][j] = dp[i - 1][j] + arr[i][j]
   • j가 i일 경우, dp[i][j] 는 삼각형의 오른쪽 끝에 위치하므로 dp[i - 1][j] 가 존재하지 않는다 ⇒ 따라서 dp[i][j] = dp[i - 1][j - 1] + arr[i][j]
4. 마지막 줄까지 계산을 완료하면, 마지막 줄 원소들 중 최대값을 출력한다 (Math.max 및 전개연산자 이용)