[백준 1904] DP 유형 : 01타일(python 풀이)01타일

1. 문제 

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

2. 입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

3. 출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

---

4. 포인트

1. 동적 프로그래밍 문제를 풀기 위해서는 점화식(인접한 항들 사이의 관계식)을 세워햐 한다.
2. 동적 프로그래밍의 점화식 풀이는 다음과 같이 매우 간략하게 짜여질 수 있다.
3. 순차적으로 풀 수 있는 문제에 대해서는 DP 이더라도 재귀를 사용하지 않아도 된다.

4. 문제 풀이

최초에는 재귀적으로 값을 확인해가면서 풀었지만 메모리 초과가 나왔다. 해당 문제는 단순히 순차적으로 다음값을 구해나가도 상관이 없기때문에 굳이 재귀적으로 풀지 않고 다음과 같이 답을 구해낼 수 있었다.

 

N = int(input())

lst =[0] * 1000001

lst[1] = 1
lst[2] = 2

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

print(lst[N] )