아래 링크의 가이드에 따라 문제를 풀고 있다.
알고리즘 가이드
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이가 한 시간에 떠오르지 않아 해설을 찾아보았다.
그런데 납득이 가지 않아 이해갈 때까지 생각해보고 글을 작성하기로 마음을 먹었다.
우선 입시?식 풀이 방법이 눈에 띄었는데, n이 1일 때 1, n이 2일 때 2, n이 3일 때 3, n이 4일 때 5... 하고 쓰다 보면 어? 피보나치구나! 하고 a[n] = a[n - 1] + a[n - 2]라고 생각할 수도 있더라.
이렇게 풀고 넘기는 것은 공부의 취지와 맞지 않아서 좀 더 고민해보기로 했다.
그렇게 고민하던 중, 너무나 수월하게 해결되어 허무함 반 기쁜 맘 반으로 글을 쓰고 있다.
그러니까, ans[n-2]에서 두 칸을 채울 수 있는 경우는 =, ||인데 =로 채울 경우 하나의 경우의 수 뿐이니 ans[n-2] * 1로 ans[n-2]와 같고, ||로 채울 경우 ans[n-2]에서 | 하나를 채운 경우와 같은 경우의 수를 가지는데, 이는 ans[n-1]인 것이다.
ans[n-3]까지 고려해야 한다고 생각해서 조금 헤맸었는데, 무척 간단히 풀리는 문제였다.
이하 코드 첨부.
N = int(input())
ans = [0 for _ in range(1001)]
ans[1] = 1
ans[2] = 2
for i in range(3, N + 1):
ans[i] = ans[i - 1] + ans[i - 2]
print(ans[N] % 10007)유사 문항 11727
- 이번엔 2 x 2 정사각형도 쓸 수 있다는 조건만 달린 문제가 나왔다.
- 다르지 않다.
- ans[n - 2]를 잘 생각해보면 거기서 =만 넣을 수 있었던 11726과는 달리 ㅁ 를 넣을 수 있다는 점이 차이점이다.
- 11726의 점화식이 a[n] = a[n-1] + a[n-2]였다면, 이번엔 ㅁ 의 존재로
a[n] = a[n-1] + 2 * a[n-2]가 된다는 것만 다르다.
