79 삐약 : 백준 9461| 파도반 수열 [바킹독 문제 풀이|DP|JAVA]

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

 

 

package BKD_0x10_DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_9461 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while(T-->0){
            int N  = Integer.parseInt(br.readLine());

            long[] dp = new long[101];

            dp[1]=1;
            dp[2]=1;
            dp[3]=1;

            if(N>=4){
                for(int i=4;i<=N;i++){
                    dp[i] = dp[i-2]+dp[i-3];
                }
            }


            System.out.println(dp[N]);

        }
    }
}

 

 

점화식 : dp[N] = dp[N-3] + dp[N-2]

 

점화식을 찾아내는 것은 수월했다. 근데 이제 자료형 이슈가 있었다

파도반 수열은 기준 값이 100일 경우 9000억 가까이 되기 때문에 int형 범위를 넘어간다. 때문에 long 으로 풀이를 진행해야 한다.