[C++] 백준 11단계 - 24267번 문제 (알고리즘의 수행 시간 6)

문제설명

 

소스코드

#include <iostream>
using namespace std;
int main()
{
    unsigned long long n;
    int count = 0;
    cin >> n;
    cout << n * (n - 1) * (n - 2) / 6 << endl << 3;
}

 

풀이

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까지의 수 중에서 중복없이 3개의 숫자를 뽑는 경우의 수와 같다. (nC₃)
• 시간복잡도는 O(N³)이다.
• 즉, 수행 횟수는 n * (n - 1) * (n - 2) / 6이고, 최고차항의 차수는 3이다.

2023.01.15 - [자료구조 & 알고리즘] - 알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O

알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O