DP - 9461(파도반 수열)

9461번: 파도반 수열 (acmicpc.net)

9461번: 파도반 수열

 

파도반 수열입니다. 1,1,1,2,2,3,4,5,7,9의 형태로 수열이 진행됨을 알 수 있고 이를 점화식으로 표현한다면, 

 

F(n) = F(n-3) + F(n-2)의 점화식이 나옴을 알 수 있습니다. 이를 Bottom-up 방식으로 풀어내면 다음과 같습니다. 

 

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


public class Main {

    static long dp[]= new long [101];


    public static long padovan(int n){
        if (n == 1 || n == 2 || n == 3) {
            return 1;
        }
        else if(dp[n] == 0){
            for(int i = 4; i<=n; i++){
                dp[i] = dp[i-3] +dp[i-2];
            }
            return dp[n];
        }
        else{
            return dp[n];
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;

        for(int i = 0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(padovan(n));
        }
    }
}

 시간초과를 방지하기 위해서 비어있는 배열이 아닌경우에는 바로 배열값을 반환하도록 해주었습니다. 또한 결과값이 커지기 때문에 long타입 배열을 선언 해 주었습니다.