[백준] 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 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()) - 2;

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

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

 

n이 3일 때 수행 횟수는 1번,

n이 4일 때 수행 횟수는 4번,

n이 5일 때 수행 횟수는 10번,

n이 6일 때 수행 횟수는 20번,

n이 7일 때 수행 횟수는 35번입니다.

수열 an이라 하겠습니다.

 

n 값에 따라 3, 6, 10, 15로 늘어나는 수열이 보입니다.

수열 bn이라 하겠습니다.

 

또 이 수열은 3, 4, 5로 늘어납니다. 이건 수열 cn입니다.

 

3, 4, 5로 늘어나는 수열의 일반항을 cn이라 할 때 cn = n + 2입니다.

 

따라서 bn = 3 + $\sum_{k=1}^{n-1}k+\sum_{k=1}^{n-1}2$ 가 되는데 계산을 하면

$\frac{n^{2}+3n+2}{2}$가 됩니다.

 

이제 an을 구할 차례입니다.

$an = 1+\frac{1}{2}\sum_{k=1}^{n-1}k^{2}+\frac{3}{2}\sum_{k=1}^{n-1}k+\sum_{k=1}^{n-1}1$

을 계산하면,

$an = \frac{n^{3}+3n^{2}+2n}{6}$이 됩니다.

 

다만 맨 처음 입력값 n이 1일 때부터 진행한 수열이 아니고 3부터 진행한 수열이기 때문에

처음에 n을 입력받고 2를 빼줘야 합니다.

 

최고 차수는 최고차항이 n³이므로 3입니다.

 

 

 

 

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

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