[Python] 백준 1904번 01타일 성공

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

01타일

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	14112	5932	4958	41.399%

문제

지원이에게 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이 주어진다.(N ≤ 1,000,000)

출력

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

예제 입력 1 복사

4

예제 출력 1 복사

5

소스코드

N = int(input())
dp = [0] * 1000001
dp[1], dp[2] = 1, 2
for i in range(3,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%15746
print(dp[N])

해설

• 처음 시도한 방법은 재귀함수 방식으로 문제를 진행하였습니다.
• 직접 문제를 읽어보고 하나씩 그려보면 규칙이 있는 것을 확인할 수 있습니다.

n = int(input())
tab = {1:1,2:2}
def zero_one(n):
    if n in tab:
        return tab[n]
    else:
        tab[n] = (zero_one(n-1) + zero_one(n-2))%15746
        return tab[n]

print(zero_one(n))

1 bit : [1] => 1개

2bit : [00],[11] => 2개

앞에서 부터 [00]을 채워 간다고 생각하면 됩니다.

3bit : [00] + [1] => 1bit

​ [1] + [00] => 2bit

​ [1] + [11]

4bit : [00] + [00 or11] => 2 bit

​ [1] + [000, 001, 100, 111] => 3bit

이런 방식으로 진행됩니다.

따라서 n비트로 구성된 경우의 개수는 n-1번 째의 개수와 n-2번 째의 개수를 더하면 됩니다.

하지만

결론은 실패

• 이번 문제를 풀면서 매번 느끼지만 재귀함수는 성능이 안좋습니다.

• RecursionError: maximum recursion depth exceeded

• RecursionError가 발생하거나 아니면 계산 속도가 느려서 시간 초과로 실패하게됩니다. 따라서 다른 방법을 찾았습니다.

N = int(input())
dp = [0] * 1000001
dp[1], dp[2] = 1, 2
for i in range(3,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%15746
print(dp[N])

• 문제에서 제시한 1,000,000개의 숫자가 들어올 수 있는 공간을 먼저 배정하였습니다. 계속 append하면 동적할당으로 계속 공간을 다시 할당해야하는 비효율이 발생됩니다.
• 각 자리에 더한 값을 for문을 통해서 인덱스를 3부터 원하는 값까지 계속 진행하면서 값을 바로 리스트에서 불러온 후 저장하는 방식입니다. 함수를 불러올 필요가 없습니다.

유사한 문제

2020/02/07 - [파이썬] - [Python] 백준 10826번 피보나치 수 4 풀이 해설

2020/02/04 - [파이썬] - [Python] 백준 2748번 피보나치 수 2 풀이 해설