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

백준 24264번과 이어지는 문제이다.

 

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

2중 for문을 사용하였고, (1~(n-1))*((i+1)~n)인 모습이다.

i+1이라고..? 이걸 어떻게 구할 것인가? n을 7으로 두고 규칙을 찾아보자.

n이 7일 때, 안쪽 for문이 실행되는 것을 시뮬레이션 한 것이다.

 

안쪽 for문이

i가 1일 때는 6번 실행 (1+1 to 7)

i가 2일 때는 5번 실행 (2+1 to 7)

...

i가 6일 때는 1번 실행 (6+1 to 7)

 

우리는 안쪽 for문(코드1)이 몇 번 실행 되는지만 구하면 되므로, 이는 1~(n-1)의 합이라고 볼 수 있다.

이는 등차수열의 합 공식을 이용해 계산식을 만들어 준다. (이미지 참고)

 

그러므로 계산식은 O(n^2)이 되므로 최고차항은 2이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        System.out.println(n*(n-1)/2);
        System.out.println(2);
    }
}