BOJ_1932 정수 삼각형

TOC {:toc}

이 글은 백준 온라인 저지의 1932번 문제를 자바스크립트(JavaScript)로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.24

메모리	시간	코드 길이
15680 KB	224 ms	803 B

단계	시작 시각	끝난 시각
문제 이해	14:16:20	14:17:28
풀이 생각	14:29:33	14:33:56
코딩	14:33:30	14:56:10

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, ...lines] = input;
const triangle = lines.map((line) => line.split(" ").map((n) => parseInt(n)));

function main() {
    let max = triangle[0];
    for (let i = 1; i < N; i += 1) {
        const tmp = [];
        triangle[i].forEach((num, j) => {
            let prevMax = 0;
            const length = triangle[i].length;

            if (j === 0) {
                prevMax = max[0];
            } else if (j === length - 1) {
                prevMax = max[length - 2];
            } else {
                prevMax = Math.max(max[j], max[j - 1]);
            }
            tmp.push(num + prevMax);
        });

        max = tmp;
    }

    return Math.max(...max);
}

console.log(main());

아이디어 & 풀이

인접해있는 윗줄의 결과값 중 더 큰 값을 더해 해당 줄을 최댓값으로 업데이트 한다.

인접해 있는 수는 현재 값과 인덱스가 같거나 하나 작은 수이다.

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

모든 계산이 끝나고 삼각형 마지막 행의 값중 최댓값을 출력한다.

피드백

줄 단위로 진행되므로 굳이 최댓값을 담아둘 임시 배열을 만들 필요 없이 triangle의 값을 직접 바꿔도 됐다.

참고 답안

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, ...lines] = input;
const triangle = lines.map((line) => line.split(" ").map((n) => parseInt(n)));

function main() {
    for (let i = 1; i < N; i += 1) {
        const length = triangle[i].length;
        for (let j = 0; j < length; j += 1) {
            let prevMax = 0;

            if (j === 0) {
                prevMax = triangle[i - 1][0];
            } else if (j === length - 1) {
                prevMax = triangle[i - 1][j - 1];
            } else {
                prevMax = Math.max(triangle[i - 1][j], triangle[i - 1][j - 1]);
            }
            triangle[i][j] += prevMax;
        }
    }

    return Math.max(...triangle[N - 1]);
}

console.log(main());

아이디어 & 풀이

위의 피드백을 반영한 코드