백준 1904 자바 DP 풀이

01 타일은 동적 계획법으로 푸는 문제이다.

 

01 타일의 특이한 점은 n에 따른 증가폭이 어디서 본 것 같은 모양새로 증가한다.

 

N = 1일 때 1개 (1)

N = 2일 때 2개 (00, 11)

N = 3일 때 3개 (100, 001, 111) 

N = 4일 때 5개 (0011, 0000, 1001, 1100, 1111 )
.....

즉, 1,2,3,5,8.... 이런 식으로 증가하는 게 피보나치 증가하는 것처럼 보인다.

이때, 점화식이 dp [n] = dp [n-1] + dp [n-2] 이므로 그대로 적용하여 풀되

46번째부터 int 범위를 벗어나므로 15746으로 나누어 나머지를 저장한다.

 

import java.io.*;

public class t1904 {

  static final int mod = 15746;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());

    int[] arr = new int[1000001];

    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;

    for (int i = 3; i <= n; i++) {
      arr[i] = (arr[i - 1] + arr[i - 2]) % mod;
    }

    bw.write(arr[n - 1] + "");

    br.close();
    bw.flush();
    bw.close();
  }
}