[Silver III] 2×n 타일링 - 11726

문제 링크

성능 요약

메모리: 32412 KB, 시간: 36 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 4월 10일 22:56:51

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

n = int(input())

rectangle = [0] * (n+1)

if n == 1:
    result = 1
    print(1)
else:
    rectangle[1] = 1
    rectangle[2] = 2

    for i in range(3,n+1):
        rectangle[i] = ((rectangle[i-1] % 10007)+ (rectangle[i-2] % 10007))  % 10007

print(rectangle[n])

보통 이런 유형의 문제를 솔루션은, 예시로 들면 1,2,3,4,5만을써서 10이라는 숫자를 만들수있는 경우의 수를 찾는 것이라고 생각하면 조금 쉽게 알아차릴수 있다.

점화식을 찾으려면 주어진 수가 뭔지 알아야 한다.
1,2,3이 주어지고 이것으로 찾으려고 한다면 dp[1], dp[2], dp[3]의 값을 찾고

dp[i] = dp[1] + dp[2] + dp[3]

라는 점화식을 도출해낼수 있다.

이 알고리즘 문제는 도형을 썼는데, 2 x n크기 이다.

n번째까지의 값을 나열해보면 앞에서 말했듯이 1,2만을 써서 n의 값을 구한다고 볼 수 있다.

그렇기에 점화식만 구한다면 간단하게 구할 수 있다. 다만 10007로 나눈 나머지값을 구해야하기 때문에

rectangle[i] = ((rectangle[i-1] % 10007)+ (rectangle[i-2] % 10007)) % 10007

이와 같이 써줘야 메모리를 많이 사용하지 않게 된다. 만약에 이 공식을 사용하지 않는다면 dp의 수가 너무 커지게된다.

(a % c) = ((b%c)+(d%c)) % c 라는 공식을 알아두면 좋다.