python 백준 1904 01타일

백준 1904번 01타일 문제

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

1904번: 01타일

 

문제 : 00와 1을 사용하여 만들 수 있는 경우의 수의 15746으로 나눈 나머지

접근법

- 타일의 개수의 따른 조합법을 찾았다

타일이 하나인 경우 조합이 1가지

타일이 둘인 경우 조합이 2가지

타일이 셋인 경우 조합이 3가지

타일이 넷인 경우 조합이 5가지 가 나왔으며

피보나치 수열처럼 f(n) = f(n-1) + f(n-2)로 움직이는 것을 확인 후 dp를 이용하여 접근

문제점 : 처음에는 top-down 방식으로 접근하였지만 백준에서 돌릴 시 재귀가 너무 깊어져 

재귀 깊이 에러가 나와 bottom-up방식으로 바꾸어주어 해결 하였다.

import sys
sys.stdin = open('inputs.text')

n = int(sys.stdin.readline())

## 딕셔너리를 활용 ##
memo = {0:0, 1:1, 2:2}

def fx(n):
    if n in memo:
        return memo[n]

    memo[n] = (fx(n-2) + fx(n-1))%15746
    return memo[n]

## top-down방식으로는 재귀에러가 나와
## bottom-up방식으로 접근하였다
for i in range(3,n+1):
    fx(i)


print(fx(n))