문제
지원이에게 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으로 나눈 나머지를 출력한다.0
풀이
다이나믹 프로그래밍(동적 계획법) 문제입니다.
처음 생각할때는 for문을 돌려주면서 2진수들을 list에 넣어준 다음 모든 list의 value에 대해서 검사를 해주면 된다고 생각했습니다. 하지만 메모리초과로 오답이 나왔고, 다른사람의 풀이에서 힌트를 얻어 풀었습니다.
해당 문제의 답은 N이 1씩 증가하면서 피보나치 수열을 이루고 있었습니다.
이때 저는, deque를 이용해서 문제를 풀기로 하였습니다.
풀이는 아래와 같습니다.
1. 처음 생각한 풀이
N=int(input())
my_list = []
for i in range(0, 2**N):
my_list.append(bin(i)[2:].rjust(N, '0')) ## bin: 2진수로 만들어주는 함수, rjust 오른쪽 정렬하고 빈칸 패딩해주는 함수
answer = 2**N ## answer를 전체 개수로 잡은뒤 조건에 부합할경우 1씩 줄여줌
for m in my_list:
if '0' in m.replace('00',''): ##'00'을 없앴음에도 0이 남아있으면 만들수 없는 이진수열이기 때문에 answer -1, Python의 string을 활용한 잡기술
answer -= 1
print(answer%15746) #15746을 나눈 나머지를 출력해줌메모리 초과로 실패.
2. 참고한 풀이
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for k in range(3,n+1):
dp[k] = (dp[k-1]+ dp[k-2])%15746
print(dp[n])N이 증가할때마다 피보나치 수열을 이루고 있다는 것을 알아챈다면 쉽게 생각 할수 있는 풀이이다.
3. 최종 풀이
from collections import deque
N = int(input())
my_list = deque([1,2], maxlen=2)
if N == 1:
print(1)
elif N == 2:
print(2)
else:
for i in range(0, N-2):
my_list.append(sum(my_list)%15746)
print(my_list[-1])deque를 이용해 공간이큰 array를 만들어 줄 필요도 없다.
다만 15746으로 나누는 부분에서 주의해야한다, 메모리 초과가 나올 수 있다.