문제
가로길이가 2이고 세로길이가 1인 직사각형 모양의 타일이 있다.
이 타일을 이용하여 세로길이가 2이고 가로길이가 n인 바닥을 가득 채우는 경우의 수 구하기 n은 60,000이하의 자연수
경우의 수를 1,000,000,007로 나눈 나머지를 반환
입출력 예시
| n | result |
|---|---|
| 4 | 5 |
접근
DP 기본 문제이다.
d[n] 의 타일링 방법은 d[n-1]의 방법들의 마지막에 세로 타일을 하나씩 추가하는 것과
d[n-2]의 방법들의 마지막에 가로타일 2개를 추가하는 방법을 더한 것이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
def solution(n):
d = [0 for _ in range(n+2)]
d[1] = 1
d[2] = 2
for i in range(3, n+1):
d[i] = (d[i-1] + d[i-2]) % 1000000007
return d[n]