[백준 1904번] 01타일 in 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 ≤ N ≤ 1,000,000)

출력

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

예제 입력 1

4

예제 출력 1

5

---

다이나믹 프로그래밍이란 것을 깜박했다... ㅋㅋㅋ

 

그냥 아무 생각없이 음... 재귀함수로 풀면 되겠네. 하고 풀었다.

n=int(input())

count=0
def solve(n,result):
  global count
  if n==result:
    count+=1
    return

  for i in [1,2]:
    if result+i<=n:
      solve(n,result+i)

solve(n,0)
print(count%15746)

00을 2로 뒀다.

1과 2를 계속해서 더해주는 방식으로 그 합들이(result) n과 같아지면 count+1하고 끝내는 재귀함수이다.

colab환경에서 답은 잘 나왔다. 하지만 역시 백준에 제출하니 RecursionError가 나왔다.

 

재귀함수를 쓸 때, recursionError가 자주 뜨는데 이는 n이 998 이상일 때 발생한다. 즉 이 문젠 재귀로 풀지말고 for문을 돌리던가 다이나믹 프로그래밍으로 풀으란 소리다.

 

그래서 다시 고민을 해본 결과 간단한 조합으로 풀 수 있겠다 생각이 들었다.

예를 들어 4의 경우 1111, 1100, 1001, 0011, 0000 5가지이다. 위에서 했던 것처럼 00을 2로 두고 푼다면 1111, 0000을 제외한 나머지 경우는 1이 2개 2가 1개로 조합의 경우가 된다.

또 5를 예로 들어보자. 11111을 제외한 1이 3개와 2가 1개의 조합 수, 1이 1개와 2가 2개인 조합 수를 풀면 총 8가지가 나온다. 1+4C1+3C2

 

이것을 코드로 구현해보았다.

n=int(input())

count_2=n//2
count_1=n%2
count=0
from itertools import combinations
for i in range(count_2,-1,-1):
  lst=[2]*i +[1]*(count_1+(count_2-i)*2)

  if i!=0:
    count+=len(list(combinations(lst,i)))
  else :
    count+=len(list(combinations(lst,count_1+(count_2-i)*2)))

print(count%15746)

itertools의 combinations을 써서 조합의 경우를 찾고 len으로 카운트 해줬다.

이것을 또 백준에 제출한 결과. 메모리초과가 떳다... ㅋㅋㅋㅋ

진짜 얼마나 똥컴을 쓴 걸로 가정하는지 모르겠다ㅜㅜ

 

결국 뭐가 문제지 하고 검색을 해봤다. 이 01타일도 피보나치수열을 따르고 있는 것을 파악했다.(진작에 한번씩 해볼걸 ㅜ)

그 후 다이나믹 프로그래밍으로 문제를 해결했다.

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])