[solved.ac 실버3] 1904_01타일 (파이썬, DP)

제한 사항

 

문제

지원이에게 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이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

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

출력

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

예제

---

나의 풀이

간단하게 설명하자면 6개 자릿수로 만들어야하는 경우에 4자리로 만들 수 있던 경우에 모두 '00'을 붙이는 경우와 5자리로 만들 수 있었던 경우에 모두 '1'을 붙이는 경우로 볼 수 있다.

결국 직전의 값과 그 앞 값을 더하면 된다.

 

감이 잘 안오면 다음과 같이 나열해보자. ('00'은 항상 한 쌍으로 오니까 보기 편하게 '0'으로 표현했다)

'''
---
1개일 때
1

---
2개일 때
0

11

--
3개일 때
01
10

111

---
4개일 때
00

011
101
110

1111

---
5일 때

001
010
100

0111
1011
1101
1110

11111

---
6일때

000

0011
0101
0110
1001
1010
1100

01111
10111
11011
11101
11110

111111

... 

d = [1, 2, 3, 5, 8, 13, ...]
'''

 

규칙성이 보이는가? 위에서 설명한 2개 전의 경우에 '00'을 붙이는 것 + 1개 전의 경우에 '1'을 붙이는 것으로 이루어지는 것을 확인할 수 있다.

d의 초기 값은 [1, 1]로 시작한다. 0자리 숫자로 만들 수 있는 경우는 1가지, 1자리 숫자로 만들 수 있는 경우도 1가지 이기 때문이다. (2개 전의 경우를 확인해야 하기 때문에 최소한 2개의 값은 초기화 후에 값을 찾아나간다)

전체 코드

d = [1, 1]
n = int(input())
while len(d) <= n:
    d.append((d[-2] + d[-1]) % 15746)
print(d[-1])

나는 d 리스트에 계속 추가하는 방식으로 작성했지만 메모리를 더 아끼기 위해서 리스트가 아닌 2개의 변수를 사용해도 좋다.

 

채점 결과