[실버3, DP] 백준 1904 - 01타일 (자바)

DP 문제는 아직도 참 어렵당

 

00과 1로 타일을 만들 수 있는 수열의 개수를 구하는 문제다.

 

https://www.acmicpc.net/board/view/84734 에서 letusshow님의 답변이 너무 좋았다. 해당 답변을 보니 이 문제의 풀이가 와닿았다.

 

타일을 만들 수 있는 경우는 2가지.

1. 00 타일이 오는 경우 - 00...으로 시작

2. 1 타일이 오는 경우 - 1...로 시작

 

길이가 N인 이진 수열의 개수'를 f(N)이라고 정의하면 f(N) = f(N-1) + f(N-2)

또한 f(0) = f(1) = 1임을 확인

 

 

 

제출 코드

import java.util.*;
import java.io.*;

public class testtest {
    static int N;
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
        process();
    }

    private static void process() {
        System.out.println(dp(N));

    }

    private static int dp(int n) {

        if(dp[n] == null){
            dp[n] = (dp(n-2) + dp(n-1))  % 15746;
        }
        return dp[n];
    }

    private static void init() throws IOException {

        N = Integer.parseInt(br.readLine());

        dp = new Integer[N+1];

        dp[0] = 0;
        dp[1] = 1;
        if(N >= 2) dp[2] = 2;
    }

}