문제:
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
*타일을 가로로 배치하는 경우
*타일을 세로로 배치하는 경우
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
풀이 방법:
이전 단계인 2xn 타일링과 같이 동적계획법을 사용해서 풀어야 하는 문제이다. n이 증가할 때마다 어떠한 규칙에 따라서 증가하는지 파악할 수 있다면 쉽게 문제를 풀 수 있다. n이 6~8까지 그려보면 대충 규칙을 찾아낼수 있다. 우선 n이 홀수 일 때는 타일링을 할 수 없다. 따라서 이 경우에는 항상 0이다.
그리고 타일로 만들 수 있는 모양이 한정적이라서 그 모양들을 여러 개 붙인 모양으로 반복이 된다. 규칙이 있는 타일은 다음과 같다.
이 타일들의 조합으로 반복이 되며 n=4일 때부터는 추가적인 몇개의 조합이 더 생기게 된다. 이는 이전 n(짝수만 생각했을 때)과 연관이 있기 때문에 다음과 같이 코드를 짤 수 있다.
1 2 3 4 5 6 7 8 9 | def solution(n): dp=[0]*(n+1) dp[0]=1 special=0 for i in range(2,n+1,2): dp[i]=dp[i-2]*3+special*2 special+=dp[i-2] answer = dp[n]%1000000007 return answer | cs |
문제 링크:
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 3. 순위 (0) | 2019.07.30 |
|---|---|
| [Programmers]Lv3. 가장 먼 노드 (0) | 2019.07.29 |
| [BOJ]2805. 나무 자르기 (0) | 2019.07.27 |
| [BOJ]1654.랜선 자르기 (0) | 2019.07.26 |
| [BOJ]10816. 숫자 카드2 (0) | 2019.07.25 |