01타일

❓문제
https://www.acmicpc.net/problem/1904

❗문제 정리
피보나치를 알아내면된다!
📑코드

n=int(input())
dp=[0]*1000001 

dp[1]=1
dp[2]=2

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

print(dp[n])

📝코드 설명

n=int(input())
dp=[0]*1000001 

자릿수 n 입력받기
최대 자릿수가 1,000,000이므로 0을 포함한 인덱스 크기 1,000,001크기의 dp테이블 만들기

dp[1]=1
dp[2]=2

초기값 넣어주기

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

print(dp[n])

3번째 인덱스부터 피보나치 계산하여 출력

🎖제출 결과

💡insight

경우의수를 세면 피보나치 수열임을 알 수 있음.