[DP] 1904 - 01타일 (실버3) with Python

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

1904번: 01타일

주저리 주저리

dp를 하두 풀어보니 이제 이런 문제는 보자마자 답이 나오기 시작한다...
나는 dp에 약했었는데(그래프랑 dp랑...그리디랑...) 집중적으로 파기 시작하니 사람이 꼭 죽으라는 법은 없는 것 같다
하지만 그래봤자 아직 골5 ~ 실버문제들...
못해도 골드 2~3까지는 가는것이 목표이다. 아자!

문제 해결

문제 해결방법은 간단한 규칙만 생각하면된다
n번째에서 둘수 있는 방법은 전단계의 영향을 받게 된다. n-1번째의 총 횟수(그러면 1하나만 넣으면 끝) n-2번째의 총 횟수(그러면 00넣으면 끝)
이렇게 생각하면 점화식이 하나 만들어진다
dp[n] = dp[n-1] + dp[n-2]
이게 끝이다.

코드

import sys
input = sys.stdin.readline
n = int(input())
mod = 15746
dp = [0 for _ in range(1000001)]
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 5
for i in range(5,n+1):
    dp[i] = (dp[i-1]+dp[i-2])%mod
print(dp[n])