[python/파이썬] 백준 1904 01타일

[문제 출처]

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

1904번: 01타일

 

[소스 코드1 - 시간 초과]

제일 처음에 접근한 방법은 dp 리스트에 길이가 1, 2, 3,... 인 이진 수열을 문자열로 저장해서 

dp[i]를 구하고자 할 때 길이가 i-1인 수열에 문자 '1'을 덧붙이고, 길이가 i-2인 수열에는 '00'을 덧붙였고,

중복이 많기에 set으로 중복을 없애서 저장해주었다.

시간 초과가 나올 수밖에 없는 코드이긴 하다.

#1904
n = int(input())

dp = [[''], ['1'],['00','11']]

for i in range(3,n+1):
  tmp = []
  for a in dp[i-1]:
    tmp.append(a+'1')
    tmp.append('1'+a)
  for b in dp[i-2]:
    tmp.append(b+'00')
    tmp.append('00'+b)

  result = list(set(tmp))
  dp.append(result)

print(len(dp[n]))

 

[소스 코드2 - 맞았습니다!!]

길이가 i인 이진 수열을 찾기 위해서 i-1과 i-2의 길이를 가진 이진수열을 이용한다.

소스 코드1과 접근 방법은 같으나, dp에 이진 수열의 개수를 저장한다.

길이가 1인 경우부터 쭉 이진 수열을 만들어보면 피보나치수열을 이루는 것을 알 수 있다.

 

주의할 점은 출력 부분에 개수를 15746으로 나눈 나머지로 출력하라는 조건이 존재한다.

이 조건을 따르지 않으면 너무 큰 숫자들이 저장되기 때문에 메모리 초과가 나온다.

dp에 저장할 때부터 15746으로 나눈 나머지로 저장해주어야 메모리 초과가 나오지 않는다. 

n = int(input())

dp = [0,1,2]
for i in range(3, n+1):
  dp.append((dp[i-1]+dp[i-2])%15746)

print(dp[n])