[백준 1904번] 01타일

문제 링크: 1904번 제목

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

 

n은 길이이므로, 1자리가 더 길면 a[n-1]의 원소마다 '1'을 붙일 수 있고, 2자리가 더 길면 a[n-2]의 원소마다 '00'을 붙일 수 있다. a[n-2]에서는 '1'을 붙이는 것을 고려할 필요가 없는데, a[n-1]의 원소에 '1'을 붙인 것과 중복되는 결과이기 때문이다.

따라서 a[n]을 '00'과 '1' 타일로 만들 수 있는 2진 수열의 개수라고 할 때, 점화식은 다음과 같다.

 

a[n] = a[n-1] + a[n-2]

 

다만 숫자가 굉장히 크니 문제에서 제시된 15746으로 계속해서 나누어주면서 계산하는 편이 좋다.

 

import java.util.Scanner;

public class Main {
    public static int tile(int n) {
        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;
        }
        return arr[n];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(tile(n));
        sc.close();
    }
}