문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
| n | result |
|---|---|
| 4 | 5 |
내 코드
def solution(n):
answer = 0
m = 10**9+7
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
dp[i] = (dp[i-2] + dp[i-1]) % m
return dp[n]아이디어
문제로 가장한 피보나치 수열 문제(DP-보텀업)
n = 0 일때 타일을 배치할 수는 없지만 경우의 수로 따졌을 때는 타일이 0개 배치됐을때를 따져줍니다.(1개)
n = 1 일때 세로로 세웠을때 1가지를 고려합니다.
n = 2 일때
1) 가로 1개
2) 세로 2개
2가지로 이는 곧 dp[2] = dp[1]+dp[0] 으로 계산이 됌 (여기서 납득이 안가면 n=3까지 보면)
n= 3 일때
1) 가로1개 + 세로1개
2) 세로1개 + 가로1개
3) 세로3개
총 3가지로 구성이 가능하며 dp[3] = dp[2] + dp[1] 로 계산이 됩니다.
따라서 이런 규칙성을 지닌 문제는 dp로 해결할 수 있습니다.
