문제
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치하는 경우
- 타일을 세로로 배치하는 경우
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예시
| n | result |
|---|---|
| 4 | 5 |
풀이
해당 문제는 사실 의도만 파악하면 구현 난이도 자체는 Lv.1과 동일할 정도의 수준이라고 생각한다. 언뜻 문제만 보면 1과 2를 가지고 n을 채울 수 있는 각각의 방법을 모두 계산해주어야 할 것 처럼 보인다. 그림을 봐도 어떤 규칙이 있는지 한눈에 파악하기가 힘들어 보인다. 사실 결론부터 말하자면 해당 문제는 피보나치 수열을 이용하여 풀 수 있다. 왜 피보나치 수열을 적용하여 풀 수 있는지 차근차근 살펴보자.
먼저 주어진 직사각형 모양의 타일은 가로 길이가 2이고 세로 길이가 1이다. 그렇다면 우리가 채워야 할 바닥의 길이가 n일 때, 우린 주어진 직사각형 타일을 이리저리 돌려가면서 아다리를 맞춰가야 할 것 이다. 이 과정을 직접 해보자.
먼저 n = 1인 경우를 생각해보자. 이때는 타일을 가로로 눕혀서 배치할 수가 없다. 따라서 배치가 가능한 경우의 수는 단 한 가지이다.
다음은 n = 2인 경우를 생각해보자. 먼저 (1) 세로로 타일을 2개 연달아 배치하는 경우의 수가 있다. 또한 가로의 길이가 2이기 때문에 (2) 눕혀서 타일을 배치하는 경우도 가능하다. 따라서 총 2가지의 경우의 수가 존재한다.
다음은 n = 3인 경우를 생각해보자. 역시 마찬가지로 (1)세로로 3개를 연달아 배치하는 방법, (2) 가로로 1개 배치 + 세로로 1개 배치, (3) 세로로 1개 배치 + 가로로 1개 배치하는 경우의 수로 총 3가지의 경우의 수가 존재한다.
다음은 n = 4인 경우로 생각해보자. (1) 세로로 4개를 연달아 배치하는 방법, (2) 가로로 1개 배치 + 세로로 2개 배치, (3) 가로로 2개 배치, (4) 세로로 2개 배치 + 가로로 1개 배치 그리고 (5) 세로 1개 배치 + 가로 1개 배치 + 세로 1개 배치로 총 5가지 경우의 수가 존재한다.
마지막으로 n = 5인 경우를 보자. 이때는 앞에서의 과정과 마찬가지로 계산하면 총 8가지의 경우의 수가 나온다.
n의 값이 1, 2, 3, 4, 5, ... 로 증가함에 따라 그 결과값이 1, 2, 3, 5, 8, ...처럼 변화하고 있다. 어디서 많이 본 수열이지 않은가? 재귀함수에 대해 처음 익힐 때 단골예제로 항상 등장하곤 하는 피보나치 수열이다.
직접 경우의 수를 따져가며 반환되는 결과가 피보나치 수열임을 알 수 있었다. 하지만 여전히 왜 피보나치 수열이 해당 문제에 적용되는지 의문이 들 수 있다. 이는 피보나치 수열을 재귀함수로 구현할 때 콜 스택(Call Stack)에 굉장히 무리가 가게 되는데, 이는 동일한 계산을 계속 반복하기 때문이다. 때문에 이를 해결하기 위해 메모이제이션(Memoization)이라는 방식을 사용하는데 쉽게 말하면 DP(Dynamic Programming)과 유사하다. 우리는 피보나치 수열을 DP로 구현하는데에서 왜 이 문제가 피보나치 수열인지에 대한 힌트를 얻을 수 있다.
다시 n = 1인 경우부터 생각해보자. 이 경우에는 의심할 여지없이 단 한 가지 경우의 수만 존재한다.
n = 2일 때는 위에서와 같이 두 가지의 경우의 수가 존재하는 것을 확인할 수 있다. 여기서 우리는 n = 2일 때의 값을 구하기 위해 이전에 구한 n = 1 일 때의 값을 활용하고 있다는 것을 파악할 수 있어야 한다. 무슨말이냐 하면, n = 2 일 때 배치 가능한 경우의 수는 다음의 두 가지이다.
- 세로로 연달아 2개를 배치하는 경우
- 가로로 위아래로 2개를 배치하는 경우
여기서 1번 경우의 수에 주목하자. 1번은 사실 n = 1일 때의 케이스에 포함되는 경우이다. n이 1 이상이라면 무조건 세로로 1개의 타일을 놓을 수가 있다. 따라서 1개의 타일을 두었을 때 남은 타일의 수는 1개가 되고, 이는 결국 n = 1일 때의 경우의 수와 동일한 값이 나올 것이다. 반면 가로로 배치하는 경우는 이전에 등장하지 않았다. 따라서 새로운 경우의 수로 1개가 더 추가되어 n = 2 일 때는 총 두 가지의 경우의 수가 된다.
보통 피보나치를 DP로 구할 때 편의를 위해 1번째 값은 1, 2번째 값은 2로 미리 초기화하여 구현하기도 한다.
그렇다면 똑같이 n = 3일 때를 살펴보자. 역시 n이 1보다 크기 때문에 세로 방향으로 타일 1개를 무조건 배치할 수 있다. 이 경우 남은 공간은 n = 2 일때와 동일하고, 우리는 앞서서 해당 결과값을 미리 구했기 때문에 그대로 활용할 수 있다. 가로로 배치하는 경우 역시 n > 2를 만족하기 때문에 1개를 무조건 배치할 수 있다. 이 경우 남은 공간은 n = 1일 때와 동일하고 이 값 역시 미리 구했기 때문에 활용이 가능하다. 따라서 다음의 점화식을 구할 수 있다.
DP[n] = DP[n-2] + DP[n-1]
(이때 n은 초기값에 따라 최소 2 또는 3 부터 시작한다)
피보나치 수열 역시 타일을 배치한다는 개념만 제외하면 위와 완벽하게 동일한 과정이다. 즉 해당 문제는 타일 배치라는 그림 속에 교묘하게 피보나치 수열을 숨겨놓은 문제라고 할 수 있다.
또한 해당 문제를 DP로 접근할 수 있는 또 다른 꿀팁이 있는데, 문제 조건을 보면 최종 결과를 1,000,000,007로 나눈 나머지 값으로 리턴해달라고 요구하고 있다. 이는 결과값이 매우 커질 수 있음을 의미하고 이러한 문제는 보통 DP 와 같은 이전 값을 활용하여 누적하는 방식의 문제인 경우가 많다. 물론 아닐 수 있는 가능성도 다분하니 그저 접근 방향을 결정할 때 한 번 스치듯 생각해보고 지나가도록 하자.
피보나치를 DP로 구현하는 방식은 이미 관련글이 많으니 해당 포스트에서는 바로 완성된 풀이로 살펴보자.
코드
function solution(n) {
return fibonacci(n);
}
const fibonacci = (n) => {
const dp = new Array(n+1).fill(0);
dp[0] = 1; dp[1] = 1;
for(let i = 2; i <= n; i++) {
dp[i] = (dp[i-2] + dp[i-1]) % 1000000007;
}
return dp[n];
}출처
