[Coding Test] 프로그래머스 - 타일링

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

 

[문제 설명]

가로길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

- 타일을 가로로 배치 하는 경우

- 타일을 세로로 배치 하는 경우

예를 들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

[제한사항]

- 가로의 길이 n은 60,000 이하의 자연수입니다.

- 경우의 수가 많아질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return 해주세요.

 

---

idea

1. 주어진 타일로 특정 길이의 공간을 채우는 경우의 수는 이항 정리로 계산 가능하다.

ex) n=5일 때,

길이 2인 타일 0개 사용 >> 4C4 : 길이 1인 타일로 채울 수 있는 경우의 수 =1 

길이 2인 타일 1개 사용 >> 4-1C2 :  길이 1인 타일로 채울 수 있는 경우의 수 =3

길이 2인 타일 2개 사용 >> 4-2C0 : 길이 1인 타일로 채울 수 있는 경우의 수 =1

--> 경우의 수는 4C4+3C2+4C0=5

 

2. n을 바꿔가면서 경우의 수를 나열

n=2) 2

n=3) 3

n=4) 5

n=5) 8

.....

--> n개 길이가 늘려가면서 경우의 수를 나열했을 때, 경우의 수가 피보나치수열과 같이 증가한다.

 

3. 피보나치 수열과 같은 방식으로 길이 n의 바닥을 채우는 경우의 수를 계산

def solution(n):
    first,second=1,1
    for i in range(2,n+1):
        temp=second
        first,second=second,second+first
    return second%1000000007

 

 

본 문제는 프로그래머스의 다른 문제인 멀리뛰기 문제와 유사하게

이항 정리로 경우의 수를 구할 수 있는 문제라서 경우의 수가 피보나치수열로 증가하는지 확인하여 풀었다.

 

https://programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기