[BOJ] 1904 01타일 - JAVA

1. 문제

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

1904번: 01타일

1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

---

2. 풀이

• 처음이 1로 시작하는 피보나치 수열이다. Fn = (Fn-1에 맨 뒤 1을 더한 값) + (Fn-2에 맨 뒤 00을 더한 값)이기 때문이다.
• 이렇게 맨 뒤에만 숫자를 붙이도록 생각한 이유는 중복을 피하기 위해서다. n=3일 때, n=2의 경우에서 앞 뒤로 1을 붙여줄 수 있지만 100, 111, 001, 111 <- 벌써 여기서부터 중복이 시작된다. 따라서 되도록 한 방향에서만 숫자를 붙이도록 했다.
• n=1일때 경우의 수는 1
• n=2일때 경우의 수는 00, 11
• n=3일때 경우의 수는 1+00, 00+1, 11+1
• n=4일때 경우의 수는 00+00, 11+00, 100+1, 001+1, 111+1

import java.io.*;

public class BOJ_1904_01타일 {
   static int[] fib;
   static int DIV = 15746;
   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

      fib = new int[N+1];
      fib[0] = fib[1] = 1;
      System.out.println(findFib(N));
   }

   private static int findFib(int n) {
      if(fib[n]!=0) return fib[n];

      return fib[n] = (findFib(n-1)+findFib(n-2))%DIV;
   }
}

---

3. 결과