백준 1904번 : 01타일 java

이 문제는 규칙을 찾아서 점화식을 만들어 푸는 다이나믹 프로그래밍 문제입니다.

이 문제에서는 N이 1일 때 1개, 2일 때 2개, 3일 때 3개 4일 때 5개 이런 식으로 만들 수 있습니다.

이때 찾을 수 있는 점화식은 오른쪽의 식과 같습니다.

 

이러한 규칙으로 늘어나는 것은 피보나치 수열의 형태와 같습니다.

따라서 저는 이러한 형태가 되도록 코드를 구현했습니다.

---

import java.io.*;

public class Main {
    static int[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        dp = new int[N+1];

        if(N == 1){
            System.out.println(1);
            return;
        }

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i<=N; i++)
            dp[i] = -1;

        tile(N);

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

    static int tile(int N){
        if(dp[N] == -1)
            dp[N] = (tile(N-1) + tile(N-2)) % 15746;
        return dp[N];
    }
}