백준 1904 01타일(Java)

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

1904번: 01타일

---

 

해석 및 팁

 

---

 

먼저 n이 1이면 1, n이 2이면 11,00 n이 3이면 100,001,111 n이 4이면 1111,1100,0000,1001,0011 이므로 개수가 피보나치수열로 늘어난다는 것을 알 수 있습니다. 따라서 15746으로 나눈 값을 구해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
  
    int n = sc.nextInt();
    int[] arr = new int[1000001];
    arr[1] = 1;
    arr[2] = 2;
    
    for(int i = 3; i <= n; i++) {
      arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
    }
    
    System.out.println(arr[n]);
  }
}