• TOC {:toc}

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

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

2023.02.26

메모리 시간 코드 길이
11944 KB 476 ms 665 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 12:54:56 13:00:58
풀이 생각 13:01:01 13:13:19
코딩 15:41:03 15:54:40 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim();

const D = parseInt(input);
const DIV = 1000000007;
const map = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3, 4],
    3: [1, 2, 4, 5],
    4: [2, 3, 5, 7],
    5: [3, 4, 6],
    6: [5, 7],
    7: [4, 6],
};
let course = Array(8).fill(0);
let count = 1;
course[0] = 1;

function main() {
    while (count <= D) {
        const tmp = [];
        for (let i = 0; i < 8; i += 1) {
            tmp.push(map[i].map((acq) => course[acq]).reduce((a, b) => a + b, 0) % DIV);
        }
        course = tmp;
        count += 1;
    }
    return course[0];
}

console.log(main());

아이디어 & 풀이

시간을 1초씩 증가하면서 각 0(정보과학관)에서 출발해 각 지점까지 갈 수 있는 경로의 수를 1,000,000,007로 나눈 값을 dp(course) 배열에 저장한다.

각 초가 늘어날 때 마다 다음 지점 i로 이동할 수 있는 경우의 수는 i와 인접한 건물로 갈 수 있는 경로의 수를 모두 더한 값과 같다.

  • 그러므로 인접한 건물을 나타내는 map을 구성하고, map[i]의 원소에 대해서
  • 각 지점의 경로의 수(현재 course 값)를 구해
  • 그 값을 더한 값을 새로운 course[i] 값으로 지정한다.
    • 값이 커지는 것을 방지하기 위해 1,000,000,007로 나눈 값을 저장한다.

이를 주어진 시간만큼 반복한 뒤 course[0] (정보과학관)의 값을 반환해 출력한다.