[JAVA] 백준 1904번_01타일

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

1904번: 01타일

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];
        dp[0] = 1; dp[1] = 1;
        if(N >= 2) {
            for (int i = 2; i <= N; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
            }
        }
        System.out.println(dp[N]);
    }
}

• BottomUp 방식으로 규칙 발견
  • N(1) : 1
  • N(2) : 00, 11 
  • N(3) : 100(1+00), 001(00+1), 111(11+1) 
  • N(4) : 0000, 1100 (→ N(2)), 1001, 0011, 1111 (→ N(3))

즉, 가용할 수 있는 숫자는 길이가 1인 1, 길이가 2인 00이 존재 
  → 1은 길이가 k-1인 dp[k-1]만큼 사용하고, 00은 길이가 k-2인 dp[k-2]만큼 사용
  → dp[k] = dp[k-1] + dp[k-2] (k > 2)