• 링크 : https://youtu.be/qLkFBk5-HrY
  

---

백준 2*n 타일링

• 링크 : https://www.acmicpc.net/problem/11726

• 문제 해결 아이디어
  - DP는 이전값을 어떻게 활용하느냐와 점화식을 어떻게 세우느냐가 핵심이다
  

• 점화식을 어케 세울지 감이 안오면 일단 경우의 수를 Time t별로 해봐라
  - 경우의 수를 보면서 패턴을 파악해라!
  - n = 1, case는 1가지
  - n = 2, case는 2가지
  - n = 3, case는 3가지
  

• 점화식을 어케 세울지 감이 안오면 일단 경우의 수를 Time t별로 해봐라
  • 경우의 수를 보면서 패턴을 파악해라!
  • n = 1, case는 1가지
  • n = 2, case는 2가지
  • n = 3, case는 3가지 {한칸을 막는 경우->2가지, 두칸을 막는 경우->1가지}
  • ...
  • 따라서 n번째 => {이전값}을 더하거나 {이전이전값}을 더한 값

따라서 다음과 같은 결론이 도출됨

"""
1. 아이디어
    - 점화식 : An = An-1 + An-2
    - N값 구하기 위해, for문으로 3부터 N까지 값을 구해주기
    - 이전값, 이전이전값 더해서, 10,007로 나눠 저장
    
2. 시간복잡도
    - O(N)
    
3. 자료구조
    - DP값 저장하는 (경우의수) 배열 : int[]
    - 최대값 : 10,007보다 작음 > INT

"""

n = int(input())
memo = [0] * 20
memo[1] = 1     # n = 1일때 2일때 경우의 수 기록
memo[2] = 2

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

---

DP 결론

• DP는 BFS DFS 이런거처럼 큰 틀은 비슷하지만
• 점화식 세우는게 중요해서 어려움
• 점화식 세우지 않고 코드부터 접근하면 무조건 실패함
• 따라서 점화식 먼저 생각해보고 진행해야함
• 이때, 생각이 안나면 경우의 수 하나씩 그려보면서 써보면서 패턴을 찾는다