[백준-11726]-[다이나믹프로그래밍] - 2 x N 타일링

문제링크 : https://www.acmicpc.net/problem/11726

이 문제는 문제만 그림이지 1과 2로 입력받은 수 N을 만드는 문제이다.

이런식으로 길이 2 * 5의  타일에 2 * 1 타일 로 길이 1을 1 * 2 타일 두개로 길이 2를 채울 수 있다.

그럼 1,2로  5를 만드는 경우의 수를 구하면 된다.

5를 1 또는 2로 만들 수 있는 경우의 수는

1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 2

1 + 1 + 2 + 1

1 + 2 + 1 + 1

1 + 2 + 2

2 + 1 + 2

2 + 2 + 1

여기서 끝이 1로 끝나는 것들 2로 끝나는 것들을 모아보면

- 1로 끝나는 것들 

1 + 1 + 1 + 1 + 1

1 + 1 + 2 + 1

1 + 2 + 1 + 1

2 + 2 + 1

끝자리 1을 제외하고 나머지는 4를 만드는 경우의 수이다.

- 2로 끝나는 것들

1 + 1 + 1 + 2

1 + 2 + 2

2 + 1 + 2

끝자리 2를 제외하고 나머지는 3을 만드는 경우의 수이다.

즉 5의 경우의 수는  4의 경우의 수 3의 경우의 수의 합이라는게 나온다.

그럼 점화식을 구해보면 아래와 같이 나온다.

sum[N] = sum[N-1] + sum[N-2]

그럼 점화식도 구했으니 코딩을 해보자.

N 의 최대값이 1000 까지 계산을 하다보면 아무리 long으로 해서 64bit형식의 타입이더라도 오버플로우가 발생한다. 

출력할때 % 10007 을 해도 계산할떄 오버플로우가 발생하니깐 합할때 매번 % 10007을 해줘서 오버플로우가 발생하지 않게 해야한다.

소스

import java.util.Arrays;
import java.util.Scanner;
 
public class E_11726 {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();
        long[] sum = new long[num+1];
        
        sum[0] = 1;
        sum[1] = 1;
        
        for(int i=2; i <= num; i++) {
            sum[i] = (sum[i-1] + sum[i-2]) % 10007; 
        }
        System.out.println(sum[num]);
    }
 
}