[알고리즘] 백준 11727번 문제(DP)

백준 11727번 파이썬

n = int(input())
# 크기가 n인 직사각형을 채우는 방법의 수
# 어느정도 점화식 노가다 필요
dp = [0]*1001
dp[1]=1
dp[2]=3
for i in range(3,n+1):
    dp[i]=dp[i-1]+2*dp[i-2]
print(dp[i]%10007)

• 점화식 생각하는게 핵심이다.

• 초반 1~3번째에서 규칙을 생각해내기.
• 생성한 규칙을 메모제이션으로 구현하기.

• DP 생성 방식은 어느정도 다 비슷하다.

• 처음 dp 배열 생성할 때 메모하는 습관.