[BOJ] 백준 24267 알고리즘 수업 - 알고리즘의 수행 시간 6 (Swift)

문제

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

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

풀이

문제의 알고리즘은 n에 영향을 받아, 중첩된 for문이 약 $n^3$번 실행됩니다.
빅오 표기법으로 $O(n^3)$ 입니다.

수행 횟수는 어떻게 될까요?

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

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

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

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

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

즉, 1 부터 n까지의 숫자중 3가지를 뽑아 중복 없이, 크기 순으로 작성하는 경우의 수가 수행 횟수가 됩니다.

123, 124, 125, 126, 127, 134, 135 ... 567

이것은 $_nC_3 = \frac{n!}{(n-3)!\times 3!}$ 입니다.

계산하면.. $\frac{(n-2)(n-1)n}{6}$ 입니다.

따라서 수행 횟수는 $\frac{(n-2)(n-1)n}{6}$
최고차항의 차수는 3 입니다. ($n^3$)

소스코드

후기

이번 문제는 수행 횟수의 공식을 찾는게 꽤나 힘들었던 문제입니다.
맨 처음에 풀었을 때는 뭔가 찍어서 공식을 유도했었는데, 차근차근 생각해서 공식을 찾아냈습니다.
수학 공부를 더해야겠다는.. 기분이 들었습니다..