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

■ 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 문제

 

출처: 백준 24267 알고리즘 수업 6 파이썬

 

■ 코드 풀이

 

개인적으로 알고리즘 수업 중에서는 이 문제가 가장 어려웠던 것 같습니다. 문제 설명에 앞서, 시간 복잡도에 대해 모르시는 분들께서는 아래 글을 천천히 읽고 와주세요.

 

[백준/Python] 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 문제

[백준/Python] 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 문제

 

이 문제는 O(n^3)의 시간 복잡도를 갖습니다. 따라서 다항식으로 표현하면 3차 다항식이 되겠네요. 수행 횟수가 조금 골치 아픈데요. 저는 노가다로 규칙을 알아냈습니다. i가 1일때부터 7일 때까지, 전부 해보니 n에서 3가지 경우의 수를 조합하는 nC3과 같은 공식이 나오더군요. 솔직히 이유는 잘 모르겠네요.

 

n = int(input())

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