문제 번호 24265번 : 알고리즘 수업 - 알고리즘의 수행 시간 4 - JAVA [자바]

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

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

 

문제 설명

 

시간복잡도를 분석하는 문제입니다.

 

문제 풀이

 

시간 복잡도에 대한 어느 정도 이해가 필요한 문제입니다.

시간 복잡도가 궁금하신 분들은 아래 게시글을 확인해 주세요.

https://kkungchan.tistory.com/321

알고리즘 - 시간 복잡도(Time Complexity)

해당 함수는 n이 7일 때 2~7까지 7번, 3~7까지 6번..1번까지 총 21번을 도는 함수입니다.

즉, 7+6+5+4+3+2+1을 도는 것입니다.

1~n의 총 합의 공식은 n(n-1)/2이 기 때문에 해당 값을 결과 값으로 넣어주면 됩니다.

시간 복잡도는

1+(n-1)+n(n-1)/2+1+1

= n²/2 +n/2 + 2

로 최고사항의 차수는 2가 됩니다.

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-1))/2);
        System.out.println(2);
    }
}

정확한 이유는 모르지만 n값을 long으로 받아야 정답 처리가 되었습니다.