[백준] 파이썬 24267 : 알고리즘의 수행시간 6

 

 

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

 

또 돌아온 알고리즘 수업.... 이번에도 sum이 몇번 반복되는지를 묻는 문제다. 

MenOfPassion 코드를 살펴보면 코드 1은 3중 for문 내에 있다. 그렇다면 제일 바깥 for문의 반복 횟수 * 중간 for 문의 반복 횟수 * 안쪽 for문의 반복 횟수를 구해주면 된다. 

i는 1부터 n - 2까지 반복, j는 i + 1부터  n - 1까지, k는 j + 1부터 n까지 반복한다. 

즉 i의 실행 횟수는 n - 2, j는 (n - 2) * (n - 1)번, k는 (n - 2) * (n - 1) * n번 실행된다. 그래서 코드 1의 횟수는 (n - 2) * (n - 1) * n회이다. 그리고 중첩된 반복문이 3번 반복되기 때문에 중복을 제거해주어야 해서 3!(=6) 을 나누어주는 것이다. 

둘째줄에 출력되는 시간 복잡도 또한 O(n^3)의 복잡도를 가짐으로 3을 출력해 주면 된다. 

 

 

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