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

문제

접근

1. 기본 초기화

1 또는 00으로만 초기화가 가능합니다.

2. 패턴 발견

N = 3 일때 첫번째 자리에 1 or 00이 올 수 있습니다.

• 1일때, 다음 2칸의 경우의 수는 N=2와 같습니다.
• 00일때, 다음 1칸의 경우의 수는 N=1과 같습니다.

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(r.readLine());
        int[] dp = new int[n + 1];

        if (n < 2) {
            System.out.println(n);
            return;
        }
        dp[1] =1;
        dp[2] =2;
        for (int i = 3; i < n+1; i++) {
            dp[i] = (dp[i-2] + dp[i-1])%15746;
        }
        System.out.println(dp[n]);
    }
}