087 2×n 타일링

첫번째 코드

 

점화식을 세울 때는 쉬운 듯 했지만 나의 점화식과 차이가 있었다.

나는 단순히 D[n] = D[n-1] + 1 (n-2에서 가로로 놓은 경우)라고 생각하였다.

하지만 D[n] = D[n-1] + D[n-2]이었는데, 생각해보니 마지막이 가로로 되는 경우 다른 배열들이 모두 달라지기 때문에 이게 맞는 점화식이다.

 

코드는 점화식을 기반으로 작성하였으나, 오류가 나서 책을 참고한 결과

처음 조건들을 주지 않아 문제가 생긴 것이었다.

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (1001)
mod = 10007

dp[1] = 1
dp[2] = 2

for i in range(3, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11726.%E2%80%852%C3%97n%E2%80%85%ED%83%80%EC%9D%BC%EB%A7%81

programmers/백준/Silver/11726. 2×n 타일링 at main · ornni/programmers