✨ Lv. 2 - 2 x n 타일링
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12900
문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
n이 4일 경우, 다음과 같이 5가지 방법이 존재합니다.
제한사항
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
풀이 코드 + 설명
단순히 조합을 이용하여 풀이하는 문제보다는 Dynamic Programming 문제에 해당합니다. 규칙을 찾기 위해 n이 1일때부터 하나씩 살펴보겠습니다.
n = 1: 1가지
n = 2: 2가지
n = 3: 3가지
n = 4: 5가지
n = 1: 8가지
...
규칙이 보이시나요? 타일을 조합하여 붙이는 가짓수는 피보나치 수열을 따르게 됩니다. 이를 바탕으로 작성한 코드는 아래와 같습니다.
function solution(n) {
let before = 0, current = 1, temp = 0;
while(n--) {
temp = (before + current) % 1000000007;
before = current % 1000000007;
current = temp % 1000000007;
}
return current % 1000000007;
}근데 왜 피보나치 수를 따르게 되는 것일까요? 이는 타일을 배치하는 경우의 점화식을 살펴보면 됩니다. 아래와 같이 n개의 타일을 붙인다고 가정하겠습니다.
그렇다면 n-1개의 타일에서 n개를 붙이려면 어떻게 해야할까요? 뒤에 타일 하나를 세로로 배치하는 경우가 될 것입니다.
n-2개의 타일에서 n개를 붙이려면 어떻게 해야할까요? 뒤에 가로로 2개 혹은 셀로 2개를 배치하는 경우일 것입니다.
다만, 세로로 2개를 배치하는 경우는 이미 n-1개를 배치하는 경우에 포함이 되므로 중복이 됩니다.
그렇다면 n-3개에서 n개의 타일을 배치하기 위한 방법은 어떻게 될까요? 이는 아래와 같습니다.
이 3가지 경우도 결국 중복이 됩니다. 첫 번째는 n-2에서 첫 번째와, 두 번째는 n-2에서 두 번째와, 마지막은 n-1과 중복이므로 고려할 필요가 없습니다.
이를 바탕으로 n번째 타일의 배치는 n-1번째 타일의 배치와 n-2번째 타일의 배치 경우의 수를 합한 값이라는 점화식을 도출할 수 있습니다.
