BOJ-1904 01타일

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

문제 소개

https://www.acmicpc.net/problem/11726과 유사한 문제이다. 1 또는 00으로 주어진 길이의 수열을 만드는 방법의 수를 15746으로 나눈 나머지를 구한다.

문제 풀이

크기가 n인 수열을 만드는 방법은 다음과 같다.

1. 크기가 (n - 1)인 수열의 끝에 1을 추가한다.
2. 크기가 (n - 2)인 수열의 끝에 00을 추가한다.

1번 방법과 2번 방법의 수를 더하면 크기가 n인 수열을 만드는 방법의 수를 알 수 있다.

이를 점화식으로 나타내면 $f(n) = f(n - 1) + f(n - 2)$ 이다. 즉, 피보나치 수열이다.

dp로 구현하였으며 방법의 수를 15746으로 나누도록 코드를 작성한다.

메모리가 초과되지 않도록 리스트에 값을 저장할때 15746으로 나머지 연산을 한 후 저장하도록 한다.

코드

def fib(n):
    if n == 0:
        return 0
    for i in range(2, n + 1):
        dp.append((dp[i - 1] + dp[i - 2]) % 15746)
    return dp[-1]


n = int(input())
dp = [1, 1]

print(fib(n))