백준 1904 : 01타일 (파이썬)

01타일

시간 제한	메모리 제한	제출	정답	맞힌 살마	정답 비율
0.75 초 (추가 시간 없음)	256 MB	55826	18282	14608	32.615%

문제

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

예제 입력 1

4

예제 출력 1

5

---

코드1

#https://teching.tistory.com/
n = int(input())
memo =[1]+[2]+[0 for i in range(n-1)]
def solve(n):
    if n >= 2:
        for i in range(2,n+1):
            memo[i] = (memo[i-1]+memo[i-2])%15746
    return memo[n]
print(solve(n-1))

코드2

# https://teching.tistory.com/
n = int(input())
num1 = 1
num2 = 1
for i in range(n-1):
    num1, num2 = num2, (num1+num2)%15746
print(num2)

해설

문제를 보자마자 규칙을 바로 찾아내기 어려워서 n을 늘려가면서 적어보았다.

이렇게 다 적어놓고 보니 피보나치수열과 같은 규칙이었다.

F(1) = F(2) = 1

F(n) = F(n-1) + F(n-2)  (n은 3 이상)

위 문제는

F(0) = F(1) = 1

F(n) = F(n-1) + F(n-2) (n은 2 이상)

우리는 https://www.acmicpc.net/problem/1003 해당 문제에서 DP를 통해 속도를 빠르게 진행할 수 있는 방법을 알아냈다.

1003번: 피보나치 함수

혹시 DP가 뭔지 모르는 사람들을 위해 https://teching.tistory.com/89에 정리를 해두었다!

동적 계획법 (파이썬)

이를 통해서 피보나치수열은 손쉽게 구할 수 있게 되었다.

하지만 단순하게 피보나치수열을 구한 뒤에 15746을 나눈 나머지를 출력한다면 메모리 초과가 발생한다.

왜냐하면 입력이 1,000,000까지 오기 때문에 다른 언어 같은 경우에는 결괏값이 애초에 인트형을 넘어가서 오류가 발생하고 파이썬은 int형의 저장공간은 무한대라서 IDE에서 돌린다면 정답은 나오지만 저 값을 저장하기 위해서 매우 큰 저장공간이 필요하기 때문이다.

그렇다면 어떻게 해야 하는가?

문제에서 출력은 15746으로 나눈 나머지를 출력한다고 쓰여있다.

출력을 이렇게 모듈러로 준경우는 배려를 해준 것이다! 최대 15746의 값의 크기만 저장하면 되는 것이다.

% 연산도 분배 법칙이 되기 때문에 각 계산의 결과를 15746으로 나눠서 저장해도 답은 같기 때문이다!

즉, 모든 n의 경우의 결과를 15746으로 나눈 나머지 값으로 저장해도 결과는 같으므로 저장공간에서 매우 큰 이득을 볼 수 있다.

이는 해시의 개념과 같은 개념인데 원하는 분들은 해시의 개념에 대해 알아보면 도움이 될 것이다!