[24265] 백준 문제풀이 - 알고리즘 수업 - 알고리즘의 수행 시간 4

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

문제

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

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

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;
}

입력

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

출력

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

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

풀이

24262번 문제와 별다른 차이점은 없다. 예제의 슈도코드를 py코드로 구현해보자.

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

코드를 보면 인자로 받은 n을 for i문에서는 n-1번까지 반복하고 for j문에서는 n번만큼 반복한다. 이 때 슈도코드에서 1은 가장 첫 index를 의미한다. 즉 0부터 시작한다. 7을 입력했다면 6번, 5번, … , 1번 순으로 반복하게 될 것이다.

즉, 수행횟수는 $6+5+4+3+2+1$ 이고 이는 등차가 $1$인 등차수열의 합과 같다. 등차수열의 합 공식인 $n(n-1)/2$ 가 수행횟수이며, 시간복잡도는 O(n^2)이다.

n = int(input())

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