[백준] 9461번_파도반 수열(Java)

문제 풀이

백준의 9461번 문제입니다. 문제 출처

(1) 문제 파악

보자마자 DP가 떠오르는 문제입니다. 이어지는 수열을 계산하면 되는 문제이지요!

(2) 문제 풀이 방법 생각하기

변이 더해져서 다음 것이 생기는거니까 앞 부분을 더해서 식을 만들어볼까? 하는 생각으로 규칙을 찾아보았습니다.

문제에 나온 예시를 통해 다음과 같은 규칙을 쉽게 찾을 수 있습니다.

\[P[a] = P[a-2] + P[a-3]\]

다만 N이 100이 되면 P[N]은 int의 범위를 넘기 때문에 long으로 타입을 지정해주어야 합니다.

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

파도반 수열 계산에 100번의 for문만 돌기 때문에 충분히 해결할 수 있습니다.

(4) 구현

입력의 크기가 작으므로 파도반 수열을 미리 계산해놓고 원하는 P(N)을 출력하는 방식으로 작성하였습니다.

import java.io.*;

public class Main {
    static long[] P = new long[101];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        calculateP();
        
        for(int i=0; i<T; i++) {
            int target = Integer.parseInt(br.readLine());
            System.out.println(P[target]);
        }
        
        br.close();
    }
    
    static void calculateP() {
		P[0] = 0;
        P[1] = 1;
        P[2] = 1;
        P[3] = 1;
        
        for(int i=4; i<=100; i++) {
            P[i] = P[i-2] + P[i-3];
        }        
    }
}