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

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

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

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

입력

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

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

예제 입력 1

7

예제 출력 1

35
3

코드1 이 35회 수행되고 알고리즘의 수행 시간이 n3에 비례한다.

n = 1
i= 1 -> j = (2)~ 6 -> k = 3 ~ 7
..
..
..
i = n-2 => j = (i+1) ~ n-1 -> k = (i+2) ~ n

n이 7일때까지 가볍게 구해보면
i-1 j-23456 k-34567
i-2 j-3456 k - 4567
i-3 j-456 k - 567
i-4 j-56 k - 67

이렇게 적는것 자체도 너무 많은게 i가 ~일때 j가 ~일때 k의 반복횟수를 구해야해서 문제 코드로 살펴보면

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

한번 그냥 범위로만 곱해보자

(n-2)x((n-1)-(i+1)+1)x(n-(j+1)+1)

즉 i는 n-2회 j는 n-1-i k는n-j회

i = 1일 때:

j는 2부터 6까지 (총 5회)
k는 j+1부터 7까지
j = 2일 때, k는 3, 4, 5, 6, 7 (5회)
j = 3일 때, k는 4, 5, 6, 7 (4회)
j = 4일 때, k는 5, 6, 7 (3회)
j = 5일 때, k는 6, 7 (2회)
j = 6일 때, k는 7 (1회)
총: 5+4+3+2+1=15
5+4+3+2+1=15

i = 2일 때:
j는 3부터 6까지 (총 4회)
k는 j+1부터 7까지
j = 3일 때, k는 4, 5, 6, 7 (4회)
j = 4일 때, k는 5, 6, 7 (3회)
j = 5일 때, k는 6, 7 (2회)
j = 6일 때, k는 7 (1회)
총: 4+3+2+1=10
4+3+2+1=10

i = 3일 때:

j는 4부터 6까지 (총 3회)
k는 j+1부터 7까지
j = 4일 때, k는 5, 6, 7 (3회)
j = 5일 때, k는 6, 7 (2회)
j = 6일 때, k는 7 (1회)
총: 3+2+1=6
3+2+1=6

i = 4일 때:

j는 5부터 6까지 (총 2회)
k는 j+1부터 7까지
j = 5일 때, k는 6, 7 (2회)
j = 6일 때, k는 7 (1회)
총: 2+1=3
2+1=3

i = 5일 때:

j는 6 (총 1회)
k는 j+1부터 7까지
k는 7 (1회)
총: 1
1

15+10+6+3+1=35회가 나온다(노가다일 경우 ㅋㅋ)

근데 공식은 익숙하지 않아서

• !은 팩토리얼

결국
i는 n-2회 j는 n-1-i k는n-j회를 구하는게
저 위의 공식으로 바뀌는 과정 자체를 이해하긴 어렵지만

총 반복횟수 = n개 중 3개를 고르는 조합의 수

로 생각해보면 위에서 노가다를 했기에 그건 이해가 될 것이다.
그걸 계산하려면 n(n-1)(n-2)/6이 공식이다~ 라고 대입해서 생각해놓자

최종 코드

# 입력
n = int(input())

def men_of_passion(n):
    # 코드1의 수행 횟수 산술 수열의 합
    count = n*(n - 1)*(n - 2) // 6

    # 최고차항의 차수는 n3 임
    highest_term = 3

    return count, highest_term

# 결과 계산
count, highest_term = men_of_passion(n)

# 결과 출력
print(count)
print(highest_term)