16936 나3곱2 (자바스크립트)

문제

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

======

문제 분석

모든 수들을 차례대로 시작 넘버로 두고 나누기 3 값과 곱하기 2 값이 존재한다면 그 다음 인덱스를 검사하는 문제이다.

이 문제의 입력 값은 최대 10^18까지 나온다는 지문이 있어서 BigInt로 처리하지 않으면 채점하자마자 틀렸다고 나온다.

정답 코드

// 3으로 나눈다 => 나눠져야 한다
// 2를 곱한다.

const main = (n, arr) => {
    const usedIdx = Array.from({ length: n }, () => false);

    const findIdx = (num) => {
        return arr.findIndex((v) => v === num);
    };

    const dfs = (curNum, result) => {
        if (result.length === n) {
            console.log(result.join(' '));
            process.exit(0);
        }

        const mod = curNum / 3n;
        if (curNum % 3n === 0n) { // 나누어 떨어지는 경우만 진행
            const idx = findIdx(mod);
            if (idx !== -1 && usedIdx[idx] === false) {
                usedIdx[idx] = true;
                dfs(mod, [...result, mod]);
                usedIdx[idx] = false;
            }
        }

        const mul = curNum * 2n;
        const idx = findIdx(mul);
        if (idx !== -1 && usedIdx[idx] === false) {
            usedIdx[idx] = true;
            dfs(mul, [...result, mul]);
            usedIdx[idx] = false;
        }
    };

    arr.forEach((v, idx) => {
        usedIdx[idx] = true;
        dfs(v, [v]);
        usedIdx[idx] = false;
    });
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map((v) => BigInt(v)); // BigInt로 변환
main(n, arr);