[Baekjoon 1904 / python / 실버3] 01타일

x = int(input())

d = [0] * (x + 2)

d[1] = 1

d[2] = 2

for i in range(3, x + 1):

    d[i] = (d[i-1] + d[i-2]) % 15746

print(d[x])

 

다이나믹 프로그래밍 문제이다. 점화식만 찾으면 아주 간단하게 해결할 수 있다.

 

계산값을 저장해둘 DP테이블(리스트 d)를 생성하고, 초기값을 넣어준다. d[1]엔 1길이의 수열에서 나올 수 있는 경우의 수의 개수, d[2]엔 2길이, d[x]엔 x길이의 수열에서 나올 수 있는 경우의 수의 개수가 들어간다.

 

타일 경우의 수를 구하는 것은 언뜻 답이 없어 보이지만, 규칙이 있다.

현재 값들에 1을 붙이고, 이전 값들에 00을 붙이면 그게 다음 값이 된다.

 

즉 N=4 일 때의 경우의 수를 구한다고 해보자.

N=2 -> ( 11, 00 )

N=3 -> (100, 001, 111)

N=4 -> (1100, 0000, 1001, 0011, 1111)

정확히 일치한다. 심지어 갯수는 피보나치 수열의 진행과 동일하다. f(N) = f(N-1) + f(N-2)이 성립한다.

 

문제가 요구하는 것은 "경우의 수의 개수"이기 때문에 따로 값을 구할 필요 없이 갯수만 출력하면 된다.

 

그리고 피보나치와 동일한 진행을 하기 때문에, 출력값이 엄청나게 길다. (N은 최대 100만)

그래서 15746으로 나눈 나머지를 출력하는데, 한번 계산할 때마다 계속 % 15746으로 나눠 주면 마지막까지 계산한 후 % 15746으로 나눴을 때와 동일한 값을 출력한다.