백준 24265번- '알고리즘 수업 - 알고리즘의 수행 시간 4' (PYTHON 풀이)

문제:

 

금주에 풀었던 시간복잡도 문제 중 가장 난이도가 높았다. 기존에는 어떻게 보면, 공식 아닌 공식으로 바로 풀 수 있었기 때문에 쉬웠는데 해당 문제는 공식에 있는 문제가 아니기 때문에 좀 더 깊이 생각해야하는 문제였다.

 

 

풀이:

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

문제의 코드를 다시 들고와보겠다. 

바깥 for문은 1부터 n-1까지 반복되고 안쪽 for문은 i+1부터 n까지 반복된다. 예제를 들어서 좀 더 쉽게 설명해보겠다.

 

n이 예제와 같이 7일 경우, 

i가 1일 때 j는 2~7까지 반복 (6번)

i가 2일 때 j는 3~7까지 반복 (5번)

i가 3일 때 j는 4~7까지 반복 (4번)

i가 4일 때 j는 5~7까지 반복 (3번)

i가 5일 때 j는 6~7까지 반복 (2번)

i가 6일 때 j는 7만 수행 (1번)

 

이렇게 반복된다.

여기서 어떤 규칙을 볼 수 있는지 살펴보면 i는 1씩 늘어나고 있고, j는 (n-1), (n-2)... 1 순서로 반복되고 있다.

이러한 규칙은 등차수열을 떠올릴 수 있는데, 등차수열의 합공식인 2n​{2a+(n−1)d} 이 식을 a=1, d=1 대입 후 정리하면 n(n-1)/2 라는 식이 도출된다. 이를 코드로 만들면 다음과 같다.

 

n=int(input())
print(n*(n-1)//2)
print(2)

입력 받은 값을 위에서 언급한대로 그냥 출력하면 된다. 이때 시간복잡도는 n^2이니까 무조건 2가 출력될 것이다.

아, 파이썬 기준 주의할 점은 '/', '//'의 차이이다. '/'는 실수 나눗셈이라 소수점까지 같이 출력되지만 '//'는 몫 연산이므로 실수/실수가 아닌 이상은 정수로 결과가 출력된다! 해당 문제는 당연히 정수가 들어가야하므로 '/'으로 입력하면 틀린다. 이 점을 유의해서 풀면 코드 자체는 어렵지 않다.