BAEKJOON #1904 01타일

이 문제의 저작권은 BAEKJOON에 있습니다.

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

 

타일의 개수가 늘어나는 규칙을 찾아야 문제를 해결 할 수 있다.

규칙을 찾아보면

n = 1, tile = 1

n = 2, tile = 2

n = 3, tile = 3

n = 4, tile = 5

n = 5, tile = 8

 

n번째 타일의 수는 (n - 1) + (n - 2) 의 타일 수와 같다는 것을 알 수 있다.

 

풀이

1. dp list생성
2. for문 돌며 계산한 값을 dp list에 저장

# 01타일
# https://www.acmicpc.net/problem/1904
"""
규칙을 찾아보면
n = 1, tile = 1
n = 2, tile = 2
n = 3, tile = 3
n = 4, tile = 5
n = 5, tile = 8 
...
"""
n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

# k번째 값을 구하기 위해 
# dp에 저장된 k-1, k-2번째 값을 합하고 
# 문제 조건에 따라 15746으로 나눔
for k in range(3, n+1):
    dp[k] = (dp[k-1] + dp[k-2]) % 15746
print(dp[n])