[백준] 1904번 : 01타일

문제

 

 

접근 방식

한 자리의 경우 : 1
두 자리의 경우 : 11, 00
세 자리의 경우 : 111, 100, 001
네 자리의 경우 : 1111, 1100, 1001, 0011, 0000
다섯 자리의 경우 : 11111, 11100, 11001, 10011, 10000, 00111, 00100, 00001

 

각 자릿수 별로 경우의 수를 적어보면 위와 같다.

 

우리가 사용할 수 있는 숫자는 한 자리인 1과 두 자리인 00 두 가지만 있는데

만약 여섯 자리의 수를 만들어야 한다 가정하면

첫자리에 1이 오면 그 뒤에는 다섯 자리의 수가 올 수 있을 테니

기존에 구해둔 다섯 자리의 경우만큼 만들 수 있을 것이고

첫자리에 00이 오면 그 뒤에는 네 자리의 수가 올 수 있으니

기존에 구해둔 네 자리의 경우만큼 만들 수 있을 것이다.

 

결국 1로 시작하는 경우와 00으로 시작하는 경우를 합쳐주면

n자리의 수를 만들 수 있는 경우의 수를 구할 수 있다.

 

점화식을 정리하면

첫자리에 1이 오는 경우는 (n-1)자리의 경우의 수가 되고

첫 자리에 00이 오는 경우는 (n-2)자리의 경우의 수가 되니

f(n) = f(n-1) + f(n-2) 가 된다.

 

풀이

public class Main {

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

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

        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]);
    }
}