[바미]알고리즘 수업 - 알고리즘의 수행 시간 5

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

24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5

---

 

코드

function menOfPassionAlgorithmPerformance(n) {
    // n을 BigInt로 변환
    const bigN = BigInt(n);
    // BigInt를 사용하여 n^3 계산
    const result = bigN ** BigInt(3);
    console.log(result.toString()); // 코드1의 수행 횟수를 문자열로 출력
    console.log(3); // 최고차항의 차수는 3
}

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

rl.on('line', (line) => {
  const n = parseInt(line, 10); // 10진수로 변환
  menOfPassionAlgorithmPerformance(n);
  rl.close();
});

문제 설명

이 문제에서는 MenOfPassion 알고리즘의 수행 시간을 분석해주면 됩니다.

코드1(sum <- sum + A[i] × A[j] × A[k];)의 실행 횟수와 이를 다항식으로 표현했을 때의 최고차항의 차수를 출력해주면 됩니다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

 

이 알고리즘은 세 개의 중첩된 for 반복문이 있으며, 각각의 반복문은 1부터 n까지 반복됩니다.
내부의 코드(sum <- sum + A[i] × A[j] × A[k]; - 코드1)는 이로 인해 총 n * n * n (또는 n^3) 회 실행됩니다.

 

이 때 문제에서 요구하는 n^3의 계산 결과가 JavaScript의 Number 타입의 안전한 정수 최대값(-2^53 + 1부터 2^53 - 1까지의 정수 범위)를 초과하기 때문에 BigInt를 사용해서 문제를 풀어야 합니다.