백준 1904. 01타일 | Python | 메모이제이션 & 바텀엄(상향식) 접근 방식 풀이

🔔 문제 설명은 백준 문제 링크로 대신합니다

1904번: 01타일

 

피보나치 수열이라 메모이제이션 방식과 바텀업 방식 둘 다로 풀어보았는데, 메모이제이션 방식은 재귀 깊이 설정(setrecursionlimit())을 안 하거나 충분한 깊이로 하지 않으면 RecursionError가 발생하고, 충분한 깊이로 하면 메모리 초과가 발생한다. 문제에서 N의 범위가 1 ≤ N ≤ 1,000,000 라고 해서 재귀 깊이를 10**7로 했더니 메모리가 초과되고, 줄였더니 런타임에러가 발생했다. 결국 메모이제이션 방식 대신 바텀업 방식으로 통과했다. 

 

처음에 결과가 100%에서 틀렸습니다 ! 가 나와서 당황스러웠는데 알고보니 내 잘못이 맞았다 ^.^; 이유는 아래에 설명!

 

 

이 문제에서 가장 어려운 부분은 이게 피보나치 수열이라는 것을 알아내는 것이었다. 

 

N=1 일 때는 1 - 1개 

N=2 일 때는 00, 11 - 2개 

N=3 일 때는 100, 001, 111  - 3개 

N=4 일 때는 0000, 1100, 1001, 0011, 1111 - 5개 

N=5일 때는 10000, 00100, 11111, 00001, 10011, 00111, 11111 - 8개

 

분명히 뭔가 규칙이 있을텐데, 하면서 30분동안 요리보고 저리보았더니 한 가지 패턴이 보였다. 

 

N=3일 때의 결과는 N=1일 때의 결과의 뒤에 00을 붙이고, N=2일 때의 결과의 뒤에 1을 붙인 것이었다.

유사하게 N=4일 때의 결과는 N=2일 때의 결과의 뒤에 00을 붙이고, N=3일 때의 결과의 뒤에 1을 붙인 것이었다.

즉, N번째 결과는 N-2의 결과에 00을 더한 것과 N-2의 결과에 1을 더한 것이고, 그 갯수는 1,2로 시작하는 피보나치 수열이다! 

 

피보나치 수열이라는 것을 깨달은 이후부터는 상향식 접근 방식으로 문제를 풀 수 있었다. (상향식 접근 방식에 대한 좀 더 자세한 설명은 백준 피보나치 수2 풀이에 기록 ) 문제에서 N번째 수를 15746로 나눈 나머지를 출력하라기에 처음부터 나눠주면서 계산해나갔다. (처음부터 나눠도 결과는 같으나 수가 더 작기에 속도가 더 빠르다) 

 

N = int(input())

if N ==1 : 
    print(1)
else :
    a= 1
    b= 2
    for i in range(2, N) :
        temp = a 
        a= b
        b = (temp+a)%15746
    print(b)

처음에 저 N==1 일때 print(1)하는 부분을 빼먹었더니 채점이 100%에서 틀렸습니다! 가 나왔다. ㅎ 언제쯤 이런 것좀 안 빼먹을 수 있으려나 ㅎㅎㅎㅎ 

 

 

메모리초과가 났지만 메모이제이션 방식으로 푼 코드도 함께 올려논다. (아니 여기선 n이 1 or 2일 때 처리 잘 해줬으면서 왜 바텀업 코드에서는 홀랑 까먹은 것일까!!!) 

import sys
sys.setrecursionlimit(10**7)
N = int(input())

def tile(n, memoization={}):
    if n ==1 or n ==2
        return n 
    
    if not memoization.get(n) :
        memoization[n] = (tile(n-2)+tile(n-1))%15746
    return memoization[n]

print(tile(N))

 

 

한줄소감: 문제 풀이 시간으로 잡아놓은 30분 제한이 끝나갈 때까지 피보나치가 너무 안 보여서 포기할까 싶을 때쯤! 피보나치 수열이 눈에 들어왔다. 기뻤다!!!!!

 

끝.