BaekJoon_1932(정수 삼각형)

문제

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

문제 풀이

배열을 피라미드 형식으로 그려서 확인 하면 훨씬 보기 편하다.

위에서 아래로 내려오면서 숫자를 더하는 방향보다는, 아래에서 위의 어떤 숫자와 더할 것인지 선택하는 방향으로 생각하면 좀 더 쉽게 접근 할 수 있다.

 

     7           -1

   3   8       -2

8   1   0     -3

 

3번째의 8은 2번째의 3과 더할 수 밖에 없다.

3번째의 0은 2번째의 8과 더할 수 밖에 없다.

3번째의 1은 2번째의 3과 8 중에서 큰 값을 더하면 된다.

 

이를 점화식으로 나타내면 아래와 같다.

j = 0 일 때, dp[i][j] += dp[i-1][j]

j = 1 일 때, dp[i][j] += dp[i-1][j-1]

나머지의 경우에는 dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j])

 

코드

const answer = ([n, ...arr]) => {
    const dp = [];
    
    for (let i = 0; i < Number(n); i++) {
        dp.push(arr[i].split(" ").map(Number));
    }

    for (let i = 1; i < Number(n); i++) {
        for (let j = 0; j <= i; j++) {
            let temp;
            if (j === 0) {
                temp = dp[i - 1][j] // 인덱스 0이면 바로 위의 인덱스 0번 숫자와 더하기
            }
            else if (j === i) {
                temp = dp[i - 1][j - 1] // 인덱스가 마지막이면 바로 위의 인덱스 마지막 숫자와 더하기
            }
            else {
                temp = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) // 위의 2개 중 큰 숫자를 더하기
            }
            dp[i][j] += temp;
        }
    }

    console.log(Math.max(...dp[n - 1]));
};

const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        // console.log(input)
        answer(input);
        process.exit();
    });

 

코드는 깃헙에서도 확인 가능합니다 :)

https://github.com/duduchi/Algorithm/tree/main/Dynamic

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.