📖Problem

11726번: 2×n 타일링

🔍Intuition

규칙성을 찾아보았다.

최종적으로 구해야 하는 답은 방법의 수이다. 따라서 dp테이블에 저장되어야 하는 값도 방법의 수가 되어야 한다.

위의 그림을 통해 규칙을 발견할 수 있다.

• n=1 → dp[1] = 1
• n = 2 → dp[2] = 2
• n = 3 → dp[3] = 3
• n = 4 → dp[4] = 5
• n = 5 → dp[5] = 8
• …

어렵지 않게 규칙을 발견할 수 있다. 이를 통해 세운 점화식은 아래와 같다.

dp[i] = (dp[i-1] + dp[i-2])

이때 문제에서 10007로 나눈 나머지의 값을 출력하라고 하였다. 이를 무시한채로 출력할 경우, 오답을 얻을 수 있다. 그리고 출력할 때만 10007로 나누면 상당히 메모리를 많이 차지하기 때문에 dp테이블을 저장할 때무터 10007로 나눠야 한다.

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

🔍Approach