백준 1904번_01타일 (Python)

문제

지원이에게 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이 있거나 00이 있는 것은 자명하다.

맨 마지막에 타일 '1'이 있는 경우, 이 마지막 1과 그 앞에 있는 N-1개의 타일들은 서로 독립적으로 존재한다. 즉, 마지막의 1 타일이 나머지들의 배치에 전혀 영향을 주지 않고, 그렇기에 나머지들은 나머지대로 자유롭게 배열할 수 있는 것이다. 마치 초콜릿에서 한 칸을 떼어내도 다른 칸들은 온전히 남아 있는 것과 같다. 따라서 맨 마지막에 타일 1이 있는 배열의 개수는 N-1만큼 이어진 타일열의 개수와 같다.

맨 마지막에 타일 '00'이 있는 경우도 동일한 방법으로, N-2만큼 이어진 타일열의 개수와 같다. 따라서 N만큼 이어진 타일열의 개수를 f(N)이라 하면

f(N) = f(N-1) + f(N-2)가 얻어진다.

거창한 것 같았지만 피보나치 수열이다...

 

코드

 

간단한 피보나치 수열이지만, 여기서 문제의 조건이 발목을 잡는다.

시간	제한 메모리
0.75 초 (추가 시간 없음)	256 MB

꽤나 까다롭다. 시간은 DP를 조금 엄격하게 다루면 쉽게 해결할 수 있을 것 같지만, 메모리는 1000000번째 항에까지 접근할 수 있으니 부족하다.

시도했던 방법을 전부 나열해보려 한다.

 

1. 재귀를 이용하는 방법

# 재귀 제한을 풀어주기 위해 setrecursionlimit를 이용한다.
import sys
sys.setrecursionlimit(1000004)

t = [None]*1000004

def tile(n):
    if n == 1:
        return 1 
    if n == 2:
        return 2
    if t[n] != None:
    	return t[n]
    return tile(n-1)+ tile(n-2)

N = int(input())
print(tile(N)%15746)

결과: 메모리 초과

 

2. 변수 2개를 이용한 반복문

앞에서 메모리 초과가 떴기에 변수를 두 개로 줄이면 메모리 초과가 안나지 않을까 생각이 들었다.

N = int(input())

#초기설정
a = 1
b = 2

#a, b 번갈아가면서 그다음 피보나치값 대입
for i in range(2, N):
    if a>b:
        b = a+b
    else:
        a = a+b

#결과적으로 더 큰 쪽이 f(N)일 것이니 그것을 출력
if a>b:
    print(a%15746)
else:
    print(b%15746)

결과: 시간 초과

 

3. for문

for문으로 코드를 작성해도 메모리 초과가 났다. 뭔가 이상해서 약간의 자료 조사를 한 결과, 너무 큰 수들이 저장되고 있어서 메모리 초과가 지속해서 나는 것이었다. 그래서 계산 과정에서 계속 15746으로 나눈 나머지를 대신 저장해야 한다고 한다.

N = int(input())

tile = [None]*(N+1) #N+1로 하는 이유는 N = 1일 경우 tile[1]에 2를 대입하는 아래의 코드에서 에러가 생김
tile[0] = 1
tile[1] = 2

for i in range(2, N):
    tile[i] = (tile[i-1]+tile[i-2])%15746 #메모리 초과 방지

print(tile[N-1])

 

리뷰

2번 방법은 아마 for문 안의 조건문 때문에 시간 초과가 났을 것 같다. 그러면 아마 1번 방법에서도 3번 방법처럼 15746을 지속적으로 나눠준다고 해도 시간 초과가 날 것이다. (재귀문 안에 자그마치 3개의 조건문이 있으니) 다만, 3번 방법은 수많은 재귀로 인해 메모리 초과가 난 것도 한몫을 한 것으로 예상되어 검증은 할 수 없었다.