1904_01타일

📌 DP 포인트

• 기존의 가능한 타일구성에서 뒤에 하나씩 붙여나가는 구성
• 이전의 것을 가져다 쓸 수 있다 → 점화식
• DP[k]를 이루는 값을 어떻게 구성할까
  • [k-1] 구성에는 1개만 더 붙일 수 있음 → [k-1]의 값을 그대로 가져와야 한다
    
  • [k-2]의 구성에는 00을 붙여서 사용할 수 있음
  • $`DP[k] = DP[k-1] + DP[k-2]`$

⚠️ Error

• 파이썬 메모리 초과 문제
  dp[i] = dp[i-1] + dp[i-2]
  → dp[i] = (dp[i-1] + dp[i-2]) % 15746
  
• 파이썬의 정수자료형은 하나의 객체이다!
  • 🍯 참고 블로그 https://velog.io/@toezilla/1D1Q-001.-Python의-int-자료형은-어떻게-범위가-무제한일까
    

---

🥳 정답코드

''' 
23.05.02 
10:00 ~ 10: 40 
'''
# 0.75초 / 256MB 
# 각 타일 -> 0 or 1 # 0 + 0 -> 00 
# N을 이루는 모든 2진수열 생성불가 

# N : 1이상, 100만이하 
N = int(input())

dp = [0] * (1000000+1)
dp[1] = 1
dp[2] = 2

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

# Output : 2진 수열 갯수를 % 15746 
print(dp[N])