백준 1932: 정수 삼각형 - javascript(dp)

문제 출처 

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

출력

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

예제 입력 1 복사

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1 복사

30

문제 풀이 힌트 

전형적인 ~~ dp 문제다. 

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

합이 최대가 되는 경로의 수의 합을 출력하라! 

 

이렇게 생각해보자. 

맨 끝에 줄 (N번째 줄)애들의 선택은 어떻게 되는가?

[4,5,2,6,5] 

1) 4는 2한테서 받아야 한다. 

2) 5는 2와 7한테서 받아야 한다. 

3) 2는 7과 4한테서 받아야 한다. 

4) 6은 4와 4한테서 받아야 한다. 

5) 5는 4한테서 받아야 한다. 

 

그런데 N-1 번째 줄이 말한다. 

우리는 지금까지 다 ~~~ 더해왔어. 우리가 선택할 수 있는 최대의 합을 말이야 ! 

 

그렇다면? 

N번째 줄에서 선택을 마지막으로 한 후, 거기서 최댓값을 구하면 되는 간단한 문제가 아닌가?? 

 

이걸 DP로 값을 계속 채워주면 된다. 

 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = Number(input.shift()); 
let graph = Array.from({length: N}).map(() => []); 
for(let i=0; i<N; i++){
    graph[i] = input[i].split(' ').map(v => +v); 
}

for(let i=1; i<N; i++){
    for(let j=0; j<graph[i].length; j++){
        if(j === 0){
            graph[i][j] = graph[i][j] + graph[i-1][j]
        }else if(j === graph[i].length -1){
            graph[i][j] = graph[i][j] + graph[i-1][j-1]     
          }else{
            graph[i][j] = graph[i][j] + Math.max(graph[i-1][j-1], graph[i-1][j])     
        }
    }
}
let answer = Math.max(...graph[N-1])
console.log(answer);

Only 문제 풀이 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = Number(input.shift()); 
let graph = Array.from({length: N}).map(() => []); 
for(let i=0; i<N; i++){
    graph[i] = input[i].split(' ').map(v => +v); 
}

for(let i=1; i<N; i++){
    for(let j=0; j<graph[i].length; j++){
        if(j === 0){
            graph[i][j] = graph[i][j] + graph[i-1][j]
        }else if(j === graph[i].length -1){
            graph[i][j] = graph[i][j] + graph[i-1][j-1]     
          }else{
            graph[i][j] = graph[i][j] + Math.max(graph[i-1][j-1], graph[i-1][j])     
        }
    }
}
let answer = Math.max(...graph[N-1])
console.log(answer);

 

알고가는 ppoint 

01. 런타임 에러 이유: 

- 이중 반복문에서 j++ 를 i++라고 오타 

- 이중 반복문에서 i=1부터 범위를 i=0 부터 범위로 했었음. 

배열 인덱스 오류: 내부 반복문에서 i가 0일 때 (i === 0)는 이전 행(i-1)에 접근하게 되는데, 이 때 음수 인덱스에 접근하게 되어 오류가 발생합니다. 즉, 첫 번째 행에서는 이전 행에 접근할 수 없습니다. 이런 경우를 처리해주어야 합니다.