[백준 문제풀이] 11726번 : 2×n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

💡 다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• 하향식 : 메모이제이션(캐싱)→재귀함수사용
• 상향식 : 전형적 형태 → 결과 저장용 리스트=DP 테이블(반복문 사용)

💡 다이나믹 프로그래밍의 조건

• 최적 부분 구조 : 큰 문제를 작은 문제로 나눠 문제 해결
• 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결

1. 소스코드

n=int(input())
dp = [0,1,2]
for i in range(3,n+1):
    dp.append(dp[i-1]+dp[i-2])
print(dp[n]%10007)