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

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

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

 

문제 설명

 

시간복잡도를 분석을 가장한 수학문입니다. 잘 응용해서 풀어봅시다.

 

문제 풀이

 

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

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

https://kkungchan.tistory.com/321

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

이 문제는 FOR문이 3개로 되어 있으니 당연히 시간 복잡도는 3입니다.(직관적으로 알 수 있죠)

문제는 몇 번 반복하는지 구하는 게 굉장히 어려운데 시그마에 대한 어느 정도 이해가 있어야 가능합니다. 저도 처음에는 쉽게 반복문으로 아래처럼 해결하려 했습니다.

import java.util.Scanner;

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

        int n = sc.nextInt();

        int count = 0;

        for(int i=1; i<=n-2; i++){
            for(int j=i+1; j<=n-1; j++){
                for(int k=j+1; k<=n; k++){
                    count++;
                }
            }
        }

        System.out.println(count);
        System.out.println(3);

    }
}

이렇게 진행하게 되면 시간 초과가 납니다. 그래서 결국 반복문 쓰지 말고 식으로 시간복잡도를 구해서 몇 번 반복하는지 알아내라는 문제라는 것을 인지하고 수열을 나열해 보았습니다.

N=1 -> 0번

N=2 -> 0번

N=3 -> 1번

N=4 -> 4번

N=5 -> 10번

N=6 -> 25번

N=7 -> 35번

1, 4, 10, 25, 35 수열을 가지게 됩니다. 해당 수열을 a_n이라고 하겠습니다. an은 3, 6, 10, 15 씩 차를 가지고 증가하게 됩니다. 해당 수열을 b_n이라고 하겠습니다. bn은 3, 4, 5 씩 차를 가지고 증가하게 됩니다. 해당 수열을 c_n이라고 하겠습니다. 아래와 같은 식으로 풀 수 있게 됩니다.

 

결국 a_n = (n³+3n²+2n)/6의 수열을 가지고 됩니다.

그래서 정답은

import java.util.Scanner;

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

        long n = sc.nextInt()-2;

        System.out.println(((n*n*n)+(3*n*n)+(2*n))/6);
        System.out.println(3);
        
    }
}