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

핵심 포인트

• 시간 복잡도

제출코드

n = int(input())

ans = 0
for i in range(1, n - 1):
  ans += (n - (i + 1)) * (n - i) // 2
print(ans)
print(3)

해설

이 문제를 풀 때 중요한 것은 주어진 문제 내의 코드를 분석하는 것 입니다. 주어진 MenOfPassion 함수는 2개의 변수 (A, n)를 입력으로 받습니다. 내부 알고리즘에서 중요한 부분은 반복문입니다. 보시면 3개의 반복문으로 구성되어 있음을 알 수 있습니다. 그리고 각 반복문 별로 서로 다른 횟수로 반복을 하기 때문에 이를 잘 파악해야합니다.

 

1). i = 1이라고 가정하면 j = 2 ~ n - 1까지 반복합니다. 그리고 다시 j = 2라고 하면 k = 3 ~ n까지 반복하기 때문에 총 (n - 3) + 1 = n - 2번 반복합니다. 이제 j = 3이라고 하면 k = 4 ~ n까지 반복하기 때문에 총 (n - 4) + 1 = n - 3번 반복합니다. 이제 j = n - 1이라고 하면 k = n ~ n까지 반복하기 때문에 총 1번만 반복합니다. 따라서, i = 1이라면 $1 + 2 + \cdots + (n - 2) = \frac{(n - 2)(n - 1)}{2}$번 반복하는 것을 알 수 있습니다. 

 

2). i = 2이라고 가정하면 j = 3 ~ n - 1까지 반복합니다. 그리고 다시 j = 3라고 하면 k = 4 ~ n까지 반복하기 때문에 총 (n - 4) + 1 = n - 3번 반복합니다. 이제 j = 4이라고 하면 k = 5 ~ n까지 반복하기 때문에 총 (n - 5) + 1 = n - 4번 반복합니다. 이제 j = n - 1이라고 하면 k = n ~ n까지 반복하기 때문에 총 1번만 반복합니다. 따라서, i = 2이라면 $1 + 2 + \cdots + (n - 3) = \frac{(n - 3)(n - 2)}{2}$번 반복하는 것을 알 수 있습니다. 

 

여기서 저희가 알 수 있는 것은 i번째 반복에서는 해당 반복문이 $\frac{(n - (i + 1))(n - i)}{2}$번 반복된다는 것입니다. 따라서, 저희가 원하는 총 반복횟수는 $\sum_{i = 1}^{n - 2} \frac{(n - (i + 1))(n - i)}{2}$가 됩니다.

 

 

참고자료 및 그림출처

백준 코딩 문제