127. 1904 (01타일)

문제요약

입력된 값을 자릿수로 하여 이진수에서 00 이 붙어 있거나 아예 없는 모든 경우의 수에 15746을 나눈 나머지를 구하라.

설명

먼저 이 문제를 이해하고 규칙을 찾는건 크게 어렵지 않다.

다음과 같이 피보나치수열을 이루고 있음을 알고 있다.

 

피보나치 하면 먼저 재귀함수가 떠 오를 것이다.

동적프로그래밍 파트에다가 숫자가 매우 크므로 동적을 적용해 보았다.

N = int(input())
memo = [0]*500

def Tile(N):
    if N == 1 or N == 2:
        memo[N] = N
        return memo[N]
    
    memo[N] = Tile(N-1)+Tile(N-2)
    return memo[N]

print(Tile(N)%15746)

결과는 실패였다.

다음과 같이 메모리 초과 혹은 런타임 에러가 발생한다.

RecursionError는 재귀를 너무 많이 하게 되면 발생하는 에러이다.

 

따라서 이 문제는 재귀함수로 푸는것은 불가능하다.

 

그러면 반복문을 사용해야한다.

N = int(input())
arr = [0] * 1000001
arr[1], arr[2] = 1, 2

for i in range(3,N+1):
  arr[i] = (arr[i-1] + arr[i-2]) % 15746

print(arr[N])

다음과 같이 배열을 초기화 하고 값을 저장하는 방식으로 진행하면 된다.

 

N에따른 결과를 바로 출력하기 위해 arr[0]은 비워 두었으며, 메모리 공간을 아끼고 싶다면

-1씩 붙여주면 된다.