DP : 백준 11726 파이썬 문제풀이

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

문제링크

정답 코드

import sys
n=int(sys.stdin.readline())
d=[0]*1001

d[0],d[1]=1,1

for i in range(2,n+1):
    d[i]=d[i-1]+d[i-2]
print(d[n]%10007)

오답노트

1. 마지막 값까지 계산되는지 확인하기
- 여기서는 d 배열을 1000이 아닌 1001까지 만들어야 한다

2. 시간제한
- DP는 시간제한 짧은 문제가 많은것 같다
- 혹시 모르니 input()보다 sys.stdin.readline()으로

3. 문제 제대로 읽기
- 10007로 나눈 값을 출력해야 하는데 값이 빨리 나오길래 그걸 안읽어서 신나게 틀렸다

비고

• 1000을 넣은 값

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

도 1초만에 나왔다! DP는 빠르군

• 나동빈님 말씀대로 강의를 듣고 같은 유형 문제들을 풀고 있는데 이번같은 문제는 읽어도 DP인지 모를것 같다. 더많이 풀어서 유형을 어느정도 익혀야겠다.