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

문제

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

입력의 크기 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를 출력한다.

예제 입력 1

7

예제 출력 1

21
2

산술 수열

연속된 항들 사이의 차이가 일정한 수열을 의미
이 차이를 공차라고 부름

너무 정의가 복잡해서 문제의 코드로 먼저 접근하면

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

1. 외부 for문의 i

• i는 1부터 n-1까지 반복
• i의 반복 횟수는 n-1

2. 외부 for문의 j

• j는 i+1부터 n까지 반복
• j의 반복 횟수는 n-(i+1) + 1 = n - i

처음에 든 의문은 응?? j의 반복 범위는 n - (i+1)인데 왜 갑자기 1을 더해주지? 였는데 이건 몇번 예시를 잡아보면 된다

예제 입력값 
n = 7일 때
i = 1이면
j = 2부터 7까지
즉 반복횟수가 7 - (1+1) + 1 = 7 - 1
1을 더해줘야만 반복횟수가 6이 됨

3. 총 반복 횟수
   i = 1이면, j는 2~n까지 반복 => n-1회
   i = 2, j는 3~n => n-2회
   ..
   ..
   ..
   i = n-1일때, j는 n->n => 1회

그러면 총 반복횟수는 (n-1) + (n-2) + ... + 1

여기서 공식이 있음 - 산술 수열이므로

시작 인덱스 - (i + 1)
끝 인덱스 - n
따라서 j가 반복하는 인덱스의 수는

반복횟수 = 끝 인덱스 - 시작 인덱스 +1

맨 처음에 적었던
끝 인덱스 n
시작 인덱스 i+1

즉

반복 횟수 = n - (i+1) + 1 = n-1

그렇다면 총 n-1개의 항목인 것이고
수열의 합 = 각 항목을 모두 더한 값임

S = k X (a 1 + a k) / 2

k는 항의 개수 = n - 1(범위)
a 1 은 첫번째 항 = n - 1
a k 는 마지막 항 = 1

즉, (n-1)x(n-1+1)/2

이므로

(n-1)xn/2

가 됨

실제 예시로도
n이 7이면 직접 세어봤을 때 21회인데
6x7/2=21

그대로 맞아 떨어진다

최고차항 -- 산술 수열을 곱해보면 n2 즉 2승이 가장 높은 수이므로 2가 나옴

최종 코드

# 입력
n = int(input())

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

    # 최고차항의 차수는 n2 임
    highest_term = 2

    return count, highest_term

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

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