ryeon

ryeon

프론트와 알고리즘 공부하는 학생입니다

백준 1932번: 정수 삼각형 - javascript

2 분 소요

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

출력

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

접근

먼저 그냥 주어진 예제를 풀어보자.
image
7+3+8+7+5 = 30으로 30이 최대값임을 그냥 눈으로 풀 수 있다. 그렇다면 이게 어떻게 생각해야 저런 경로를 가질까?

  • 1번째는 7밖에 없으므로 7이 최대다.
  • 2번재는 3과 8이 있는데 왜 8을 골랐을까. 그건 우리가 3번째줄의 8과 1을 이미 봐버렸기 때문이다. 즉, 우리는 3번째 줄을 보고 2번째 줄의 선택을 한 셈이다.

물론 그 다음에 2번째 줄에서 8을 골라 내려가는 방향이 더 좋은 선택일 수 도 있다.
이 경우는 n값이 5밖에 안되는 삼각형이기 때문에 가볍게 풀 수 있는 것이고, 사실은 각 줄에 대해 모든 결과값을 알아야 최대값이 되는 선택을 할 수 있다. 그럼 방금은 왜 설명한건데

다시 문제로 돌아가서 모든 경우를 구하는 방법을 새로 생각해본다.
image
위 의 그림처럼 3번째 줄에서 1로 가는방법은 2번째 줄에서 3을 통해서 가는 방법과 8을 통해서 가는 방법 2가지가 있다.
즉, dp[i][j]는 dp[i-1]줄의 [j]와 [j-1]중 큰 값과 더해서 나올 수 있다.

dp[i][j] = 원본[i][j-1] + Math.max(dp[i-1][j], dp[i-1][j-1])

이런 점화식을 얻게 된다. 그런데 1 왼쪽의 8같은경우는 선택권이 없다.
무조건 3을 택해야한다.
이처럼 위의 점화식을 각 계단의 제일 왼쪽의 수나 제일 오른쪽에 위치한 수에도 적용시키고 싶지만, 그대로 넣으면 우리는 배열의 -1값이나 undefined된 값을 참조하게 되는 불상사가 발생한다.
그러면 양쪽 끝에 0을 추가 해주면 어떨까.
어차피 주어지는 정수범위는 0이상 9999이하라고 했으니 0을 넣으면 상관없지 않을까?
image
이렇게! 조금 정리를 하자면
image
이런 형태를 띄게 된다.
이제 i=0부터 n-1까지 반복문을 돌린 뒤 마지막 줄인 dp[n-1]의 max값을 반환해주면된다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let answer = '';
  let n = input.splice(0,1);
  for(let i=0;i<n;i++){
    input[i] = input[i].split(' ');
  } 
  answer = int_angle(n, input);
  console.log(answer)
  process.exit();
});

function int_angle(n, arr){
  let dp = [];
  for(let i=0;i<n;i++){
    let tmp = new Array(3+i).fill(0);
    dp.push(tmp);
  }
  dp[0][1] = arr[0][0];
  for(let i =1;i<n;i++){
    for(let j=1;j<=(i+1);j++){
      dp[i][j] = arr[i][j-1]*1 + Math.max(dp[i-1][j], dp[i-1][j-1])
    }
  }  
  return Math.max(...dp[n-1]);
}

댓글남기기

참고