[백준] 알고리즘 수업 - 알고리즘의 수행 시간 5

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

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

---

문제 정의

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

해당 코드를 python3 형태로 바꾸면 아래와 같이 표현할 수 있다.

def MenOfPassion(A, n):
    sum = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                sum += A[i] * A[j] * A[k]
    return sum

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드 1의 수행 횟수를 출력한다.
둘째 줄에 알고리즘의 수행 시간이 상수 시간이 소요되면 0, n에 비례하면 1, n2에 비례하면 2, n3에 비례하면 3, n3보다 큰 시간에 비례하면 4를 출력한다.

---

개인적인 해석

<알고리즘 수업 - 알고리즘의 수행 시간 5> 문제는 반복문이 세 번 포함되어있는 문제이다.

따라서 <알고리즘 수업 - 알고리즘의 수행 시간 3>을 응용하면 조금 쉽게 풀 수 있겠다.

---

개인적인 풀이

해당 코드 블럭을 n≤5인 조건에서 n, i, j를 나타내 보면 아래와 같이 나열할 수 있다.

n = 5
i = [0,1,2,3,4]
j = [0,1,2,3,4]
k = [0,1,2,3,4]

i = 0
i00 i01 i02 i03 i04 = 5
i10 i11 i12 i13 i14 = 5
i20 i21 i22 i23 i24 = 5
i30 i31 i32 i33 i34 = 5
i40 i41 i42 i43 i44 = 5
i = 1
i00 i01 i02 i03 i04 = 5
i10 i11 i12 i13 i14 = 5
i20 i21 i22 i23 i24 = 5
i30 i31 i32 i33 i34 = 5
i40 i41 i42 i43 i44 = 5
i = 2
i00 i01 i02 i03 i04 = 5
i10 i11 i12 i13 i14 = 5
i20 i21 i22 i23 i24 = 5
i30 i31 i32 i33 i34 = 5
i40 i41 i42 i43 i44 = 5
i = 3
i00 i01 i02 i03 i04 = 5
i10 i11 i12 i13 i14 = 5
i20 i21 i22 i23 i24 = 5
i30 i31 i32 i33 i34 = 5
i40 i41 i42 i43 i44 = 5
i = 4
i00 i01 i02 i03 i04 = 5
i10 i11 i12 i13 i14 = 5
i20 i21 i22 i23 i24 = 5
i30 i31 i32 i33 i34 = 5
i40 i41 i42 i43 i44 = 5

n = 4
i = [0,1,2,3]
j = [0,1,2,3]
k = [0,1,2,3]

i = 0
i00 i01 i02 i03 = 4
i10 i11 i12 i13 = 4
i20 i21 i22 i23 = 4
i30 i31 i32 i33 = 4
i = 1
i00 i01 i02 i03 = 4
i10 i11 i12 i13 = 4
i20 i21 i22 i23 = 4
i30 i31 i32 i33 = 4

i = 2
i00 i01 i02 i03 = 4
i10 i11 i12 i13 = 4
i20 i21 i22 i23 = 4
i30 i31 i32 i33 = 4

i = 3
i00 i01 i02 i03 = 4
i10 i11 i12 i13 = 4
i20 i21 i22 i23 = 4
i30 i31 i32 i33 = 4

n = 3
i = [0,1,2]
j = [0,1,2]
k = [0,1,2]

i = 0
i00 i01 i02 = 3
i10 i11 i12 = 3
i20 i21 i22 = 3
i = 1
i00 i01 i02 = 3
i10 i11 i12 = 3
i20 i21 i22 = 3

i = 2
i00 i01 i02 = 3
i10 i11 i12 = 3
i20 i21 i22 = 3

n = 2
i = [0,1]
j = [0,1]
k = [0,1]

i = 0
i00 i01 = 2
i10 i11 = 2
i = 1
i00 i01 = 2
i10 i11 = 2

n = 1
i = [0]
j = [0]
k = [0]

i = 0
i00 = 1

모든 조합을 표기하면 줄 수가 늘어나기 때문에 i 반복문은 간단히 문자열로 대체하여 표기하였다.

복잡해 보이는 규칙으로 보이지만 간단하게 표현할 수 있을 것이다.

ManOfPassion 알고리즘은 배열 A와 입력값 n이 주어졌을 때 배열의 모든 조합을 3번 곱하는 코드이다.

 

이러한 조건에서 입력값 n에 따른 수행 횟수 N을 도출하면 아래와 같다.

n = 1, N = 1                            = 1 * 1 * 1
n = 2, N = 8 = sum(2,2) * 2             = 2 * 2 * 2
n = 3, N = 27 = sum(3,3,3) * 3          = 3 * 3 * 3
n = 4, N = 64 = sum(4,4,4,4) * 4        = 4 * 4 * 4
n = 5, N = 125 = sum(5,5,5,5,5) * 5     = 5 * 5 * 5
n = 6, N = 216 = sum(6,6,6,6,6,6) * 6   = 6 * 6 * 6
n = 7, N = 343 = sum(7,7,7,7,7,7,7) * 7 = 7 * 7 * 7

입력값 n이 증가함에 따라 시행 횟수 N은 n*n*n으로 계산이 가능하고, 소요 시간은 (n)^3에 비례하여 증가하게 되므로, 제출 형식에 맞게 코드를 작성하면 아래와 같이 표현할 수 있을 것이다.

import sys

input = sys.stdin.readline().rstrip()
n = int(input)

print(n*n*n)
print(3)

---