[python/파이썬] 백준 24266 24267 알고리즘 수업 - 알고리즘의 수행시간

[문제 출처]

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

24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5

 

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

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

 

 

[문제 풀이]

 

✅ 소스 코드 - 24266

 

n이 주어질 때 주어진 알고리즘은 n^3번 수행되며, 알고리즘의 수행시간은 n^3에 비례한다.

n = int(input())

print(n**3)
print(3)

 

✅ 소스 코드 - 24266

 

n에 따라 수행 횟수가 증가하며, 삼중 for문이므로 수행시간은 n^3에 비례한다.

수행 횟수는 

i = 1

j = 2 , k = 3, 4, 5, ... n  --> n - 2

j = 3 , k = 4, 5, 6, ... n  --> n - 3

...

j = n - 1 k = n  --> 1

 

i = 2

j = 3 , k = 4, 5, 6, ... n  --> n - 3

j = 4 , k = 5, 6, 7, ... n  --> n - 2

...

이런 식으로 진행되므로,      

(n-2) * 1 + (n-3) * 2 + (n-4) * 3 +... 1 * (n-2) 번이 수행된다.

n = int(input())
sum = 0
num = n-2
for i in range(1, n-1):
  sum += (num * i)
  num -= 1

print(sum)
print(3)