(백준 알고리즘 문제풀이) 1904번 01타일

문제

문제 링크

 

문제 접근

• 0, 1이 쓰여진 낱장의 타일 -> 00, 1 이 쓰여진 낱장의 타일
  goal: N이 주어졌을 때, 가질 수 있는 모든 가짓수
  output: 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지
• N의 개수
  1(1): 1
  2(2): 00, 11
  3(3): 001, 100, 111
  4(5): 0011, 0000, 1100, 1111, 1001
  5(8): 00001, 10000, 11100, 11111, 10011, 11001, 00100, 00111
• 점화식
  An = A(n-2)  + A(n-1)

코드

메모리 초과 코드

import sys
sys.setrecursionlimit(10**6)


def fib(N, memo):
    if N == 1:
        return 1
    elif N == 2:
        return 2
    else:
        if N not in memo:
            memo[N] = (fib(N-2, memo) + fib(N-1, memo)) % 15746
            return memo[N]
        else:
            return memo[N]


N = int(sys.stdin.readline())
memo = dict()

result = fib(N, memo)
print(result)

통과 코드

import sys


N = int(sys.stdin.readline())
tile = [0] * 1000001
tile[1] = 1
tile[2] = 2
for i in range(3, N+1):
    tile[i] = (tile[i-2] + tile[i-1]) % 15746

print(tile[N])

 

느낀점

점화식의 형태가 피보나치형으로 나와서 dictionary와 recursive 함수를 사용하기로 먼저 생각을 했었다. 하지만 메모리 초과 문제로 인하여 리스트의 개수를 문제에 맞게 한정적으로 변경을하고 리스트 안에 들어가는 int형이 클수록 메모리가 많이 들어가기 때문에 저장할 때부터 15746을 나누어 줌으로써 메모리 문제를 해결할 수 있었다. 어떠한 코드를 작성하더라도 메모리를 효율적으로 사용할 수 있는 방법을 생각해봐야겠다.