[백준/Python] 24267 알고리즘 수업 - 알고리즘의 수행 시간 6

[백준/Python] 24267 알고리즘 수업 - 알고리즘의 수행 시간 6

풀이 코드 및 설명

n = int(input())
print(int((n * (n-1) * (n-2))/6))
print(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;
}

위 알고리즘의 시간 복잡도를 구하면 된다

n = 7 일 때,
i = 1,2,3,4,5
j = 2,3,4,5,6
k = 3,4,5,6,7

-> 위 경우 1부터 n까지 숫자 중 3개를 뽑아서 크기 순으로 작성하는 경우의 수와 동일하다.

즉,\binom{n}{3} 과 같다.

nC3 = \binom{n}{3} = \frac{n!}{(n-3)! \cdot 3!} = \frac{n(n-1)(n-2)}{6}