백준 9461 - Java

import java.util.Scanner;

public class BJ9461 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); //테스트수 입력
        long[] pado = new long[101]; //n이 1까지므로.

        pado[1] = 1;
        pado[2] = 1;
        pado[3] = 1;

        for(int i=4; i<101; i++){
            pado[i] = pado[i-2] + pado[i-3];
        }

        for(int i=0; i<T; i++) {
            int N = sc.nextInt();
            System.out.println(pado[N]);
        }
        sc.close();
    }
}

 

고등학교때 풀던 점화식이 생각나는 문제다. 

규칙성을 찾아보면 P(n) = P(n-2) + P(n-3)이 나오게 되었다.

그걸 기반으로 사전 입력을 통해 O(1) 시간 복잡도를 만들었다.

하지만 처음에 pado 를 Integer 배열로 만들었다. 하지만 계속 worng answer이 나왔지만 이유를 알 지 못했다. 그래서 배열의 크기가 문제인건가 하고 long으로 바꾸어 보았더니 성공하였다. 이래서 오답률이 꽤나 나왔나보다.