문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
과정
먼저 예제에 나왔던 n = 9의 경우를 생각해봤다.
| 1x2 타일 | 2x1 타일 | 경우의 수 | 식 |
|---|---|---|---|
| 9개 | 0개 | a 9개를 배치하는 경우의 수 | 9! / 9! |
| 7개 | 1개 | a 7개와 b 1개를 배치하는 경우의 수 | 8! / (7! * 1!) |
| 5개 | 2개 | a 5개와 b 2개를 배치하는 경우의 수 | 7! / (5! * 2!) |
| 3개 | 3개 | a 3개와 b 3개를 배치하는 경우의 수 | 6! / (3! * 3!) |
| 1개 | 4개 | a 1개와 b 4개를 배치하는 경우의 수 | 5! / (1! * 4!) |
위의 표와 같이 다중 집합의 순열을 통해 풀면 될 것 같았다. 이러한 접근 방법을 구현한 코드는 아래와 같다.
import math
x = int(input())
res = 0
for i in range(0, x+1, 2):
res += int(math.factorial((i//2)+(x-i))/(math.factorial(i//2)*math.factorial(x-i)))
print(res%10007)하지만 역시나 또 실패.. (성공했으면 여기 안 올렸겠지)
최종 코드
아니 분명 맞는 것 같은데 자꾸 ‘틀렸습니다’가 떠서 인터넷에 있는 정답 코드와 답을 비교해보니 숫자가 커지니까 답이 다르게 나왔다.
디버깅해본 결과 확실한 이유는 모르겠지만 factorial을 사용하니까 숫자가 너무 커져서 e (문과라 가 나오게 되는 순간부터 답이 달라지는 듯 했다.e가 뭔지 모르지만 대충 큰 수라는 뜻인듯)
이것저것 시도해 봤지만 이 방법으로는 구현이 힘들 것 같아서 답을 찾아보니 피보나치 수열을 이용하면 간단하게 풀 수 있는 문제였다. 역시 DP는 1부터 답을 쭈욱 적어나가다 보면 풀리는 것이었다. 이 과정을 넘겼더니 피보나치 수열로 풀 수 있다는 사실을 알 수 없었던 것 같다.
왜 피보나치 수열 형식으로 답이 나오는지를 생각해보면 경우의 수가 아래와 같기 때문이다.
n = 4인 경우를 생각해보자.
n = 2인 경우에 “b”를 추가하는 경우와 n = 3인 경우에 “a”를 추가하는 경우가 있을 수 있다. “||”인 경우는 “aa”와 같으므로 생각하지 않는다. 결국 dp[n-2] + dp[n-1] = dp[n]이 되어 피보나치 수열로 해결할 수 있다.
x = int(input())
list = [1, 2, 3]
if x <= 3:
print(list[x-1])
else:
for i in range(3, x):
list[0] = list[1]
list[1] = list[2]
list[2] = list[0]+list[1]
print(list[2]%10007)
이 문제의 교훈은 ==일단 1부터 답을 적어보자== 인듯.