문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
제한 사항
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
문제를 보고 든 생각
적어보면 뭔가 규칙이 보이지 않을까 싶었다.그래서 무작정 노트에 타일을 그렸다.
나의 아이디어
규칙이 보이긴 보였다.n이 짝수일 때마다 새로운 규칙이 만들어졌고, 타일이 늘어나는 개수도 규칙적인 모습이 있었다.하지만 이건 코드로 짤 수가 없는 규칙이라는 생각이 들었고 분명 다른 규칙성이 있을 것 같았다.
답답한 마음에 결국 검색을 이용했다.
검색을 통해 알게 된 내용
내가 규칙성을 찾기 위해 노트에 적은 그 내용들이 이미 정답을 말해주고 있었다.정답은 열의 크기가 바뀔 때마다 변하는, 만들 수 있는 조합의 총 개수의 규칙성을 찾는 것이었다.즉, 타일의 크기당 조합할 수 있는 총 개수를 확인하면 규칙성을 찾을 수가 있었다.
하지만 나는 정말 딱 그것만 확인을 하지 않았다...총 개수에 연관성이 있을 거라고는 전혀 생각하지 않았기 때문이었다...
검색을 통해 알게 된 풀이
n = int(input())
table = [0] * 1001
table[0] = 1
table[1] = 2
for i in range(2, n):
table[i] = (table[i-2] + table[i-1]) % 10007
print(table[n-1])코드는 내가 작성했지만, 아이디어는 검색을 통해 알 수 있었다.
결과
느낀점
진짜 너무 아쉽다.
스스로 충분히 풀어낼 수 있는 문제였다.
그냥 좀만 더 들여다 볼 걸 그랬다.
다음부터는 답답해도 참아보자.
