문제:
가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우
직사각형 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
풀이 방법:
보통 이러한 문제는 패턴이 있기 때문에 패턴을 찾으려고 했다.
n이 1일때 1가지 방법, 2일 때 2가지 방법, 3일 때 3가지 방법, 4일 때 5가지 방법, 5일 때 8가지 방법...
1,2,3,5,8,13,.....
n이 증가함에 따라 방법의 갯수는 피보나치 수열을 따르면서 증가하고 있었다. 즉 피보나치를 활용해서 풀면 된다. 다음과 같이 간단하게 구할 수 있다.
1 2 3 4 5 | def solution(n): a,b=1,1 for i in range(n): a,b=b,a+b return a%1000000007 | cs |
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 3.타일 장식물 (0) | 2019.02.23 |
|---|---|
| [Programmers]Lv 2. 숫자 야구 (0) | 2019.02.22 |
| [Programmers]Lv 2. 위장 (0) | 2019.02.20 |
| [Programmers]Lv 1.N으로 표현 (0) | 2019.02.19 |
| [Programmers]Lv 2. H-Index (0) | 2019.02.18 |