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

문제풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

interface Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        long n = Long.parseLong(br.readLine());

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

알고리즘의 복잡도를 공부하는 문제입니다.

 

n이 7이라고 가정할 때 첫 번째 for 문은 1부터 6까지 반복합니다.

두 번째 for 문에서는 i가

1일 경우 j는 2부터 7까지 6번,

2일 경우 j는 3부터 7까지 5번,

...,

5일 경우 j는 6부터 7까지 2번,

6일 경우 j는 7 한 번을 수행하여 총 21번 수행합니다.

다른 수들을 이런 식으로 해서 비교해 보면 n이 주어질 경우 수행 횟수는

1부터 n-1까지의 합이 됩니다.

가우스의 덧셈을 활용하면 1부터 n-1까지의 합은 (n * (n - 1)) / 2임을 알 수 있습니다.

 

n²/2이 최고차항이므로 최고 차수는 2입니다.

 

 

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

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4