프로그래머스 - 2 x n 타일링 (연습문제)

프로그래머스 - 거스름돈 (연습문제)

문제 설명

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

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

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

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

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

제한사항

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

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

---

입출력 예

nresult

4

5

입출력 예 설명

입출력 예 #1 다음과 같이 5가지 방법이 있다.

 

 

 

 

---

내가 푼 Solution

처음 문제를 접했을 때는 세로 길이가 1일 때와 2일 때를 전부 나눠 풀 생각이었으나,

각 n 의 경우의 수를 따져보면

n = 1일 때 1가지

n = 2 일 때 1가지

n = 3 일 때

112, 211 2가지

n = 4일 때

1111, 1122, 2211, 2112, 2222 5가지

n = 5일 때

11112, 11222, 21122, 22112, 22211, 22222, 21111, 11211 8가지로 피보나치를 만족하는 것을 알 수 있다.

따라서 DP 알고리즘을 이용한 피보나치 문제로 풀어낼 수 있었다.

주의할 점은 경우의 수가 클 경우 숫자가 크면 연산속도가 느려지게 되기 때문에

매 result를 구할 때 1,000,000,007로 나누어준다.