💡문제를 보고 처음 든 생각

규칙성이 있을 것 같다는 생각이 들었습니다. 보통 규칙성 있는 경우 점화식 형태로 나타낼 수 있고 이를 재귀함수로 풀되, 제한 시간이 0.75초이므로 메모이제이션을 이용하면 시간 제한에 걸리지 않을 것이라고 생각했습니다.

🔨트러블 슈팅

규칙을 찾기 위해 크기 N=1,2,3...인 경우를 넣어보았습니다. 중간에 계산 실수들이 있어서 규칙성을 발견하지 못하고 헤매다가 검색을 했습니다. 다시 계산을 해보니 N=1이면 1, N=2이면 2, N=3이면 3, N=4이면 5, N=5이면 8 과 같이 나타났고 이는 f(N)=f(N-2)+f(N-1)의 형태인 것을 알 수 있었습니다. 바로 피보나치 수열입니다.

하지만 단순히 여러 개를 나열해서 규칙성을 찾아서 문제를 해결하기에는 논리적으로 찝찝함이 있었습니다. 다시 한 번 검색을 해서 다음과 같은 답을 얻었습니다. 조건에 맞는 N자리 수를 구하기 위해서는 조건에 맞는 (N-2)자리 수에 00을 추가하거나 조건에 맞는 (N-1)자리 수에 1을 추가하면 되는 것 입니다. 이 때 수가 중복되는 경우가 생기는데, 이를 방지하기 위해서는 수를 추가할 때는 항상 맨 뒤에 붙이면 중복이 제거가 됩니다.

참고 블로그

예를 들어, N=4를 구하고자 한다면, N=3인 경우 가능한 숫자는 100, 001, 111이고 N=2인 경우 가능한 숫자는 00, 11 입니다. 이 때 N=3인 경우의 뒤에는 1을, N=2인 경우의 뒤에는 00을 붙여줍니다.

1001, 0011, 1111
0000, 1100

이를 통해 N=4를 만족하는 수는 총 5개 임을 알 수 있습니다.

피보나치 수열임을 깨닫고 메모이제이션과 재귀를 이용하여 문제를 제출했으나 recursion error가 발생했습니다. 처음에는 recursion 횟수에 limit이 걸린줄 알고 최대값을 변경하여 다시 제출하니 시간 초과가 발생했습니다.

이유를 잘 모르겠어서 다시 검색을 해보았습니다.
다이나믹 프로그래밍에서는 문제를 해결할 때 Top-Down(하향식)방식과 Bottom-Up(상향식)방식이 있습니다.
참고 블로그

하향식은 구하고자 하는 결과부터 시작합니다. 피보나치 수열을 예로 들자면 fibo(10)을 구하고 싶으면 fibo(9)와 fibo(8)을 알아야 합니다. fibo(8)을 모르기 때문에 fibo(8)을 구하기 위해서는 fibo(6)과 fibo(5)를 알아야하고 fibo(9)을 구하기 위해서 다시 fibo(8), fibo(7)을 구해야 합니다. 이렇게 결과값부터 초기값인 fibo(1), fibo(2)까지 내려가는 방식을 하향식이라고 하고 주로 재귀 형태로 나타납니다.


상향식은 하향식과 반대로 초기값부터 시작합니다. 우리가 fibo(1), fibo(2)값을 알고 있으므로 fibo(10)을 구하기 위해 fibo(3)을 구하고 fibo(4),fibo(5)...을 차례대로 구하는 것 입니다. 밑에서부터 위로 올라가기 때문에 상향식이라고 하며 반복문 형태로 나타납니다.

두 방식에는 장단점이 존재합니다. 하향식의 경우 재귀 형태로 구현이 되기 때문에 점화식을 한 눈에 보기 쉽게 표현할 수 있습니다. 하지만 재귀라는 방식이 시간이나 메모리 효율상 좋지 않다는 단점이 있습니다. 상향식의 경우 시간과 메모리 상 효율적이라는 장점이 있습니다. 따라서 이번 문제는 상향식을 이용하여 문제를 해결했습니다.

💻소스 코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
dp = [0]*1000001
dp[1] = 1
dp[2] = 2

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

N = int(input())
func(N)
print(dp[N])