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

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

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

---

문제 정의

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

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

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

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

입력

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

출력

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

---

개인적인 해석

<알고리즘 수업 - 알고리즘의 수행 시간 4> 문제는 조건이 추가된 반복문이 두 번 포함되어있는 문제이다. 따라서 <알고리즘 수업 - 알고리즘의 수행 시간 3> 문제보다 조금 까다롭게 보이지만 규칙을 천천히 찾으면 어렵지 않게 해결할 수 있을 것이다.

---

개인적인 풀이

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

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

01 02 03 04 05 06   6
12 13 14 15 16      5
23 24 25 26         4
34 35 36            3
45 46               2
56                  1


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

01 02 03 04 05  5
12 13 14 15     4
23 24 25        3
34 35           2
45              1

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

01 02 03 04 4
12 13 14    3
23 24       2
34          1

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

01 02 03    3
12 13       2
23          1

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

01 02   2
12      1

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

01  1

n = 1
i = []
j = []

0 0

확실히 조금 복잡한 규칙이 나온다.

MenOfPassion 알고리즘은 배열 A와 입력값 n이 주어졌을 때 모든 조합이 아닌 i < j 인 조건의 조합을 곱하는 코드로 보인다.

 

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

n = 1, N = 0                             = 0    = ( 1 * (1 - 1) ) / 2
n = 2, N = 0 + 1                         = 1    = ( 2 * (2 - 1) ) / 2
n = 3, N = 0 + 1 + 2                     = 3    = ( 3 * (3 - 1) ) / 2
n = 4, N = 0 + 1 + 2 + 3                 = 6    = ( 4 * (4 - 1) ) / 2
n = 5, N = 0 + 1 + 2 + 3 + 4             = 10   = ( 5 * (5 - 1) ) / 2
n = 6, N = 0 + 1 + 2 + 3 + 4 + 5         = 15   = ( 6 * (6 - 1) ) / 2
n = 7, N = 0 + 1 + 2 + 3 + 4 + 5 + 6     = 21   = ( 7 * (7 - 1) ) / 2

여기서는 수학의 점화식 개념을 염두해 두면 수행 횟수 N의 계산식을 쉽게 도출할 수 있을 것이다.

위와 같은 규칙은 수열의 시그마 공식을 참고하면 쉽게 도출해 낼 수 있다.

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

import sys

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

print((n*(n-1)//2)
print(2)

---