[백준] 11726 _ 2XN 타일링

 

 

이 문제는 경우의 수가 생각이 부분 부분 생각이 나지 않아서 꽤 많이 고민한 문제이다.

타일을 하나하나 그리면서 보면서 풀어보았다.

 

 

 

생각이 안났던 경우의 수는 가로로 눕힌 타일이 2개이상 존재한다는 것을 늦게 깨달았다.

그래서 4개이상의 타일로 계산을 할 때 2개씩 눕히면서 경우의 수를 고려해야 했다.

 

다음과 같이 그림으로 표현하다 보면 규칙이 발생한다는 것을 알 수 있다.

 

3개이상의 타일을 사용할 때 부터 규칙이 바로 앞 순서의 개수와 앞 앞 순서의 개수를 더하면 현재 타일로 계산할 수 있는 경우의 수를 구할 수 있다는 규칙이 보인다.

 

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13 

...

 

이런 규칙이 보인다.

 

그래서 현재의 경우의 수를 이 전과 전전 경우의 수를 더해서 나올 수 있는 코드로 풀었다.

 

package solved_ac.Sliver;

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int N = Integer.parseInt(br.readLine());
        int result = f(N);
        System.out.println(result);
    }

    public static int f(int n){
        int[] fibo = new int[1001];
        fibo[1] = 1;
        fibo[2] = 2;

        for(int i = 3; i <= n; i++) {
            fibo[i] = (fibo[i - 1] + fibo[i - 2])%10007;
        }
        return fibo[n]%10007;
    }
}