[백준] 1904번 문제 (01타일) 파이썬(Python) 풀이

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

1904번: 01타일

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])

경우의 수를 차근 차근 구해보니 규칙을 발견할 수 있었다.

입력받은 숫자 n에 대하여 규칙은 아래와 같다.

 

n	2진 수열의 개수
1	1
2	2
3	3
4	5
5	8
6	13
7	21

위의 표를 식으로 정의하면 아래와 같이 정의될 수 있다.(단 n이 3이상이면)

dp[n] = dp[n - 1] + dp[n - 2]

 

이제 식을 구했으니 dp로 적용하면 문제의 답을 구할 수 있다.