[BOJ] 11726. 2×n 타일링

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

11726번: 2×n 타일링

 

 

1. 해결방법

"""
1. 아이디어
- a1 : 1, a2 : 2, a3 : 1 + 2 = 3
- 점화식을 유추 : an = an-1 + an-2
- for문으로 3부터 N까지 값을 구함
- 이전 값과 이전이전 값을 더해서 10007로 나눈 나머지를 print

2. 시간복잡도
- O(2N) == O(N)
"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline

n = int(input())

n_list = [0, 1, 2]

for i in range(3, n + 1):
    n_list.append((n_list[i - 1] + n_list[i - 2]) % 10007)

print(n_list[n])

DP 문제이다.
점화식을 떠올리기 너무너무 힘든데, 방법이 n을 1부터 차근차근 대입해서 규칙을 찾는 방법이 이 문제에서는 효율적인 것 같다.

다른 문제를 풀지 않아서 감은 안잡히지만 계속 풀어서 익숙해져야겠다.