[코딩테스트]백준 - 정수 삼각형(1932)

문제

정수 삼각형(1932)

해결한 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = input[0] / 1
let max = 0
if (n === 1) {
    console.log(input[1] / 1)
    return
}

let triangleElements = []
for (let i = 1; i < input.length; i++) {
    triangleElements.push(input[i].split(' ').map((e) => +e))
}
for(i=1; i<n; i++){
    for(let j=0; j<=i; j++){
        if(j === 0) triangleElements[i][j] += triangleElements[i-1][j]
        else if (i === j) triangleElements[i][j] += triangleElements[i-1][j-1]
        else {
            triangleElements[i][j] += Math.max(triangleElements[i-1][j-1], triangleElements[i-1][j])
        }
        if(max < triangleElements[i][j]) max = triangleElements[i][j]
    }
}

console.log(max)

풀이

※ 다이나믹 프로그래밍으로 해결한다.

1. 삼각형을 계산해내려가며 점화식을 만들 규칙을 찾는다.

삼각형을 한층한층 내려갈 때마다 가장 왼쪽과 가장 오른쪽을 제외하고는 모두 중복되어 더해진다.

ex. 예를 들면,

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

이렇게 생긴 삼각형을 살펴보자.

• 첫번째 : 7

        7

• 두번째: 3 8
  • max(7+3, 7+8)

        7
     10   15

여기까지는 별 문제 없이 계산할 수 있다.

• 세번째: 8 1 10

            7
         10   15
   18   max(11, 16)   15

가장 왼쪽(18)과 가장 오른쪽(15) 값은 중복되어 계산되지 않기 때문에 그대로 해도 무방하지만
가운데에 있는 값들은 최댓값을 취해주어야 한다.

왜냐하면 1이

• 7+3+1
• 7+8+1

로 중복 계산되기 때문이다.
이 중 최댓값을 취해야 한다.

따라서 코드를 짤 때

• 값이 가장 왼쪽, 오른쪽에 해당한다면 => 윗층의 값과 더해주기
• 그렇지 않다면 => 윗층에서 중복 계산하는 원소 중 최댓값과 더해주기

를 염두하며 작성하면 된다.

2. 최댓값을 출력한다.

나는 삼각형을 한층한층 내려가며 값을 구할 때마다 최댓값을 함께 계산했다.

😥 알고리즘.. 역시 어렵다..
조금만 소홀해도 잘 생각나지 않는구나 ㅜㅜ