JAVA 백준 24265 알고리즘 수업 - 알고리즘의 수행 시간 4 (시간복잡도)

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

 

문제는 위와 동일.

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 루프로 돌아가는 부분을 계산해서 출력한다.
중첩된 for 루프가 있으므로 최고차항의 차수는 n²이다.

 

처음 제출한 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextInt();
        long result = 0;

        for (int i = 1; i <= n - 1; i++) {
            for (int j = i + 1; j <= n; j++) {
                result += 1;
            }
        }

        System.out.println(result);
        System.out.println("2");
    }
}

for 루프를 따라서 돌렸는데 이렇게 하지 않고 답이 나오는 계산 식을 찾아서 써야 되는 것 같다.

 

최종 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextInt();

        System.out.println((n * n - n) / 2);
        System.out.println("2");
    }
}

몇 번 계산해보니 이렇게 계산하면 답이 나온다. (n * n - n) / 2