Softeer [Level 3] 수퍼바이러스 {언어 : JavaScript} [BigInt]

문제 링크

https://softeer.ai/practice/6292

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const inputData = [];

rl.on('line', (line) => {
    inputData.push(line.split(" ").map((e) => Number(e)));  
}).on('close', () => {
    const [k, p, n] = inputData[0];
    const divide = BigInt(1000000007);
    // 1초 10초 100초 ... 10**16초
    // 10초는 1초를 10제곱
    const bigIntP = BigInt(p);
    const dp = Array(17).fill(BigInt(1));
    for (let i = 0; i < 10; i++) {
        dp[0] = (dp[0] * bigIntP) % divide;
    }
    
    for (let j = 1; j < 17; j++) {
        for (let l = 0; l < 10; l++) {
            dp[j] = (dp[j] * dp[j-1]) % divide;
        }
    }
    const stack = [];
    let count = n;
    while (count >= 1) {
        stack.push(count % 10);
        count = Math.floor(count / 10);
    }
    const answer = stack.reduce((sum, e, idx) => {
        let tmp = BigInt(1);
        for (let m = 0; m < e; m++) {
            tmp = (tmp * dp[idx]) % divide;
        }
        return (sum * tmp) % divide;
    }, BigInt(k)).toString();
    console.log(answer);
    process.exit(0);
});

풀이 방법

1. 0.1초당 p배씩 증가하므로 n이 10^16인 경우 10^17번 연산을 해야한다.
   1. 이렇게 계산 할 수도 있지만 대략 10^8(1억)번이 1초라고 생각하면 10^8초???
   2. 결국 수작업으로 하나하나 계산하는 방식은 선택할 수 없다.
2. 다음 고려할 부분은 10^8 * 10^8 이상인 경우
   1. 자바스크립트의 안전한 정수 범위는 −9,007,199,254,740,991부터 9,007,199,254,740,991까지 (약 9×10^15)
   2. 따라서 BigInt를 사용해야 한다.
3. 계산하는 방법은 다음과 같다.
   1. 1초 일때는 p^10 => 이를 계산한 값을 pt이라고 하면
   2. 10초 일 때는 p^10^10 = pt^10
   3. 이런식으로 10^16초까지 구해서 dp에 넣는다.
   4. dp[0]이 1초 = p^10
4. 이후 10의 자리수를 뒤에서부터 stack에 넣고 배열을 만든다.
   
   1. 1876 = stack{6, 7, 8, 1}
   2. reduce를 이용해서 누적 값을 구한다.
   3. dp[0]^6 * dp[1]^7 * dp[2]^8 * dp[3]^1 * K % 1000000007
5. 값을 toString()으로 변환하고 출력하면 끝!
   1. BigInt를 그대로 출력하면 1827n이렇게 나온다.

느낀점

• 숫자가 10^16 언저리에서 계산하면 BigInt없이도 될거라고 생각했는데 아니었다.
• 9*10^15정도 되면 BigInt를 쓰도록 하자.