문제: https://www.acmicpc.net/problem/1904
풀이
N=1, (1) - 1개
N=2, (00, 11) - 2개
N=3, (001, 100, 111) - 3개
N=4, (0011, 0000, 1001, 1100, 1111) - 5개
이전에 만들어둔 타일에 00을 붙이거나 1을 붙임으로써 새 타일을 만들 수 있다.
그러나 i번째 타일을 만든다고 하면, i-1번째 타일에 00을 붙일 수는 없다.
그러므로 i-2번째 타일에 00을 붙이고, i-1번째에는 1을 붙여야 한다.
00과 1을 붙여도 개수는 변함이 없다.
따라서 i번째 타일의 가짓수 = (i-2번째 타일의 가짓수) + (i-1번째 타일의 가짓수) 라는 식이 나온다.
dp[i] = dp[i-2] + dp[i-1]
문제에서 요구한 것처럼 개수를 15746으로 나눈 나머지를 출력해야 하는데, 주의할 점은 결과값만을 나누어줘선 안된다.
n=1000000일 경우 많은 메모리를 차지하기 때문에 반복문 안에서 미리 나머지 연산을 해주는 것이 필요하다.
소스코드
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * 1000001
dp[1], dp[2] = 1, 2
for i in range(3, n+1):
dp[i] = (dp[i-1] + dp[i-2]) % 15746
print(dp[n])