백준 11726 : 2xn 타일링 (Python)

본문 링크

N=int(input())

dp=[1,2]

for i in range(2,N):
    dp.append( (dp[i-2]+dp[i-1])%10007)

print(dp[N-1]%10007)

📌 어떻게 접근할 것인가?

이런문제는 일단 최소 n=5 일때까지 시뮬레이션을 직접 돌려봐야한다.

그러면 [1,2,3,5,8] 이라는 값이 나올텐데 유심히 보면 피보나치 수와 같은 원리이다.

이 문제를 처음부터 보자말자 피보나치라는걸 알아차린 사람은 없을것이다.

하지만 직접 경우를 구해보면 출제자의 의도를 알 수 있다.

✅ 코드에서 주의해야할 부분

• $dp$ 값을 10007로 나눈 값을 출력한다.