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

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

---

코드

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

const result = ( BigInt(input) * BigInt(input - 1) * BigInt(input - 2) ) / BigInt(6);
console.log(`${result}\n${3}`);

문제 설명

문제는 주어진 MenOfPassion 알고리즘에 대한 수행 시간을 분석하고, 그 결과를 특정 형식으로 출력하는 문제인데요.

MenOfPassion 알고리즘은 세 개의 중첩된 for 반복문을 사용하여 특정 계산을 수행하는데  각 반복문은 다음과 같이 구성됩니다

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

• 첫 번째 반복문은 1부터 n-2까지 반복합니다.
• 두 번째 반복문은 i+1부터 n-1까지 반복합니다.
• 세 번째 반복문은 j+1부터 n까지 반복합니다.

이러한 구조는 각 i에 대해 j와 k가 선택될 수 있는 가능한 모든 조합을 반복하며, 이 경우 코드1의 실행 횟수는 n에 대한 3차 다항식으로 나타낼 수 있습니다.

 

코드1의 수행 횟수는 각 i 값에 대해 가능한 j와 k의 조합 수의 총합입니다.

기본적으로 각 i 값에 대한 j와 k의 가능한 조합 수를 더하는 것과 동일하며, 이는 결국 n개의 요소에서 순서에 상관없이 3개를 선택하는 조합의 수, 즉 nC3과 같죠.

그러므로 조합의 수 nC3는 다음 공식으로 계산됩니다.