백준 24267 파이썬, 시간복잡도 O(n^3), nC3

백준 24267 - 알고리즘 수업 - 알고리즘의 수행 시간 6

문제

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

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

24267번

답안 코드 :

n = int(input())
print(n * (n - 1) * (n - 2) // 6)
print(3)

 

백준 / 문제 / 단계별로 풀어보기 / 11단계 시간 복잡도

생각 : 

# 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;
# }

# MenOfPassion 알고리즘을 보면 총 반복문이 3번이니 두번째 줄은  3

################### 이거 말고 다른 풀이

 

n = int(input())
print(((n-2)*(n-1)*(2*n-3)+3*(n-1)*(n-2))//12)
print(3)

###############

# 6 을 예시로 들어보겠습니다.

# 첫 번째 for문은 1, 2, 3, 4 까지 실행이 되겠네요.

# 첫 번째 for문이 1일 때,
# 두 번째 for문은 2, 3, 4, 5 까지 실행이 됩니다.

# 그렇다면 첫 번짜 for문이 1, 두번 째 for문이 2 일 때는?
# 세 번째 for문이 3, 4, 5, 6 까지 실행이 됩니다.

# 첫 번짜 for문이 1, 두번 째 for문이 3 일 때는?
# 세 번째 for문이 4, 5, 6 까지 실행이 됩니다.

# 즉, 1 부터 n까지의 숫자중 3가지를 뽑아 중복 없이, 크기 순으로 작성하는 경우의 수가 수행 횟수
# 123, 124, 125, 126, 134, 135 ... 456

# nC3