[🥈3 / 백준 1904 / 파이썬] 01타일

 

1904번: 01타일

 

문제

지원이에게 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으로 나눈 나머지를 출력한다.

 

예제 입력 4

예제 출력  5

 

풀이

 

00 타일과 1 타일을 조합하여 n에 맞는 조합의 수를 찾아내는 문제이다.

 

먼저 규칙을 찾아보기 위해 00타일과 1타일을 DFS로 조합하는 함수를 만들어보았다.

 

n = int(input())

tile = ""

def dfs(STR):
    global tile
    if len(tile) > n:
        return
    
    if len(tile) == n:
        print(tile)
        return
    
    for i in ["00","1"]:
        temp=tile
        tile += i
        dfs(tile)
        tile=temp

dfs(n)

 

입력하는 숫자에 따라 n에 해당하는 조합을 찾아준다. 

 

각 n 별로 숫자를 세보았다.

 

7번째까지만 구했는데 규칙이 보인다.

 

피보나치 수열이다.

 

0개는 원래 0개 조합일 테지만, 1이라고 하고 피보나치 수열을 while문으로 만들어보자.

 

import sys
fib = [1,1]

n = int(sys.stdin.readline())

while(len(fib) <= n):
    i = len(fib)-1
    fib.append((fib[i-1]+fib[i])%15746)
print(fib[n])

 

15746으로 나눈 나머지를 출력해야하는데, 정답을 구한 뒤 나눠도 되지만 그렇게 한다면

 

n이 클 시 수가 지나치게 길어져 계산 시간도 길어질 뿐더러 메모리 초과가 발생한다.

 

위같이 수열 리스트에 미리 나눈 값을 더해줘도 값은 동일하게 나온다.