[프로그래머스] LV.4 3 x n 타일링 (JS)

문제

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

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

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

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

제한

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예시

n	result
4	11

풀이

앞서 Lv.3 난이도에 랭크된 2 x n 타일링 문제의 업그레이드(?) 버전이다. 동일한 포맷의 문제에 DP를 이용해 푸는 것도 유사하다. Lv.3 난이도의 이전 문제는 사실상 피보나치 수열을 구하는 것이기에 의도를 파악하면 어렵지 않게 구현이 가능했다. 그러나 이 문제는 2줄에서 3줄로 변경되었을 뿐인데 고려해야 할 사항이 많아졌다. 하나하나씩 차근차근 살펴보도록 하자.

1) 경우의 수

먼저 간단하게 경우의 수를 나열해보자. 이전 문제에서도 경우의 수를 나열해보니 피보나치 수열과 동일하다는 힌트를 얻을 수 있었다. 이번에도 역시 그런 요행(?)을 바라면서 n이 [1, 2, 3...]일때 몇 개의 방법이 있는지 세어보자.

1. n = 1 일 때
   • 어떠한 방법도 불가하다. 따라서 0가지 경우의 수가 존재한다.
2. n = 2 일 때
   • 총 3가지 경우의 수가 존재한다.
   • 상단에 타일 2개 세로배치 + 하단에 타일 1개 가로배치
   • 상단에 타일 1개 가로배치 + 하단에 타일 2개 세로배치
   • 타일 3개를 연달아 가로배치
3. n = 3 일 때
   • 어떠한 방법도 불가하다. 따라서 0가지 경우의 수가 존재한다.
4. n = 4 일 때
   • 문제의 입출력 예 설명과 같이 총 11가지 방법이 존재한다.

이번에는 앞 문제와 달리 어떤 규칙이 보이지 않는다. 아무리 짱구를 굴려봐도 이와 같은 순열을 보였던 규칙이 떠오르지 않는다... 그렇다면 눈물을 머금고 어떤 규칙이 숨어있는지 기를 쓰고 찾아보도록 하자.

2) 반복되는 규칙

일단 가장 먼저 쉽게 떠올릴 수 있는 규칙은 n이 홀수일 땐 어떤 방법도 불가능하다는 점이다. 이는 당연한 말인데, 3줄을 채우기 위해서는 반드시 가로로 배치된 타일이 필요한데, 가로로 타일을 배치하면 폭을 2의 배수만큼 필요로 하므로 홀수일 땐 구성이 불가하다.

따라서 우리는 n이 짝수일 때만 경우의 수를 구할 수 있다. 위에서 n = 2 일때와 n = 4 일때의 경우의 수를 각각 살펴보았다. 이들의 결과값은 각각 3가지와 11가지임을 알 수 있는데, 이들 사이의 연결고리를 찾아보자.

문제에서 제공하는 이미지를 살펴보자. 이를 3개 단위로 나누어 살펴보면, 9가지의 경우의 수는 각각 3개 단위로 n = 2 였을 때 배치가능한 타일을 고정으로 삼고 있는 것을 볼 수 있다. 즉 11가지 경우의 수에서 9가지의 경우의 수는 다음과 같다.

• n = 2 일때 경우의 수는 총 3가지이다. 각각의 경우의 수를 A, B, C라고 해보자.
• A 고정 + A | B | C => (3가지)
• B 고정 + A | B | C => (3가지)
• C 고정 + A | B | C => (3가지)

그리고 나머지 2가지 경우의 수는 n = 2 일때는 등장하지 않았던 패턴임을 알 수 있다. 이 규칙을 다음과 같이 정리해볼 수 있다.

• n이 짝수인 경우에만 타일링 구성이 가능하다.
• n = 2 일때는 3가지 패턴이 가능하고 이는 기본 출발값이다.
• n = 4 일때는 다음의 경우로 나누어 생각할 수 있다.
  • n = 2 x n = 2 구성으로 타일링을 구성하는 경우 (= 3 x 3 = 9)
  • n = 4 구성으로 타일링을 구성하는 경우 (= 2)

n = 4 라는 것은 결국 n = 2 으로 구성된 2개의 사각형을 채우는 문제로 분할할 수 있다. 이때 n = 2의 경우의 수가 3가지이기 때문이 3 x 3 = 9가지의 경우의 수가 존재하게 되는 것이다. 그러나 n = 4 일때 이전 n = 2 에서는 없었던 새로운 패턴이다. 예시 이미지를 통해 이 경우는 총 2가지가 존재하는 것을 알 수 있다. 따라서 총 경우의 수는 11가지가 된다. 여기서 우리는 다음의 규칙을 발견할 수 있다.

• n을 구성하는 이전 타일링 조합들 각각의 곱
• n자체로 만들 수 있는 새로운 패턴의 가짓수
• 위 두가지 값을 더한 결과값이 모든 경우의 수

이전 타일링의 경우의 수를 활용하기 때문에 우리는 DP를 적용하여 문제를 풀 수 있다는 것을 캐치할 수 있다. (물론 이전 문제와 동일 포맷이기 때문에 DP를 사용하는 것은 그 이전부터 캐치할 수 있었겠지만...) 다만 우리가 살펴본 것은 n = 4 였을때만 이었는데, 이를 좀 더 확장해서 n = 6 일때 역시 규칙을 적용해보자.

n = 6 일때는 다음의 과정으로 구분할 수 있을 것이다.

• n = 4 x n = 2 (11 x 3 = 33가지)
• n = 2 x *n = 4* (???)
• n = 6으로 만들 수 있는 새로운 패턴 (2가지)

이때 두 번째 과정은 왜 ???일까? 첫 번째 과정과 똑같이 33으로 계산할 수 없는 것일까? 정답은 똑같이 계산할 수 없다이다. 왜냐하면 그 과정에서 중복값이 생기기 때문이다. n = 4로 구성할 수 있는 모든 타일링에는 사실 n = 2로 구성할 수 있는 타일링이 포함되어 있다는 것을 앞서 살펴보았다. 따라서 n = 4 x n = 2 와 n = 2 x n = 4는 사실상 같은 모양의 타일링이기 때문에 이는 중복되는 값이다. 하지만 두 번째 과정에서 *를 사용해 *n = 4*처럼 특이하게 표현한 이유가 있다. 왜냐하면 n = 4일때 이전에 등장하지 않았던 새로운 패턴 2가지를 아직 고려하지 않았기 때문이다. 즉 *n = 4*는 여기서 새로운 패턴 2가지를 의미한다. 따라서 n = 2 x *n = 4* 의 결과값은 6가지가 된다. 따라서 n = 6일때 경우의 수는 33 + 6 + 2 = 41가지가 된다.

이때 한 가지 의문이 들 수 있는데, n = x 일때 x로 만들 수 있는 새로운 패턴의 경우의 수는 항상 2가지를 보장하는 것일까? 정답은 그렇다이다. 수학적으로 증명하면 좋겠지만, 본인의 수학 능력이 그렇게 뛰어나지 않기 때문에 그림으로 살펴보자.

n = 4일때 새로운 패턴 2가지 모양을 사이트에서 주의깊게 살펴보자. 이들은 각각 상단과 하단에 가로로 연달아 배치된 타일로 구성이 되어있다. 그리고 이와 같은 배치는 오직 n = x일때 x인 경우에만 새롭게 가로로 연달아 x번 배치한 타일의 경우의 수가 위/아래로 2가지가 가능하다는 것을 알 수 있다. 따라서 새로운 패턴은 항상 고정적으로 2가지가 되는 것이다.

마지막으로 n = 8일때의 과정을 살펴보고 점화식을 직접 세워보도록 하자. 위의 과정으로 말미암아 다음의 과정이 요구되는 것을 파악할 수 있다.

• n = 6 x n = 2 (41 x 3 = 123가지)
• n = 4 x *n = 4* (11 x 2 = 22가지)
• n = 2 x *n = 6* (3 x 2 = 6가지)
• n = 8일때 새로운 패턴 (2가지)

따라서 총 153가지의 경우의 수가 존재하는 것을 알 수 있다.

3) 점화식

점화식을 찾기 까지 험난한 여정이었지만, 성공적으로 규칙을 찾아냈다. 이 규칙을 적용하여 DP 알고리즘에 적용할 점화식을 만들어보자. 이미 위에서 자세히 살펴보았기 때문에 바로 점화식을 보도록 하자. 새로운 패턴이 만들 수 있는 경우의 수가 항상 2가지라는 점을 유의하면 다음과 같이 점화식을 세울 수 있다.

DP[N] = DP[N-2]*DP[2] + DP[N-4]*2 + DP[N-6]*2 + ... DP[2]*2 + 2;

즉 처음의 경우에만 바로 이전에 구한 타일링 경우의 수와 n = 2일때 경우의 수를 곱해주고, 나머지는 모두 2씩(짝수만 경우의 수가 존재하므로) 줄어들면서 n = 0이 될 때까지 2와 곱해주는 것을 알 수 있다. 그리고 마지막 역시 고정적으로 2가지가 존재하기 때문에 이 값을 더해주고 있는 것을 알 수 있다.

위 점화식을 그대로 사용해서 반복문을 돌려도 테스트 케이스를 통과할 수 있다. 그러나 우리는 여기에 조금의 메모리 최적화를 해보자. 사실 n의 최대값이 5000이기 때문에 굳이 최적화를 할 필요는 없다.

4) 최적화(?)

최적화라는 말이 부끄럽지만 그래도 조금이나마 공간복잡도를 줄일 수 있는 방법은 홀수인 경우를 아예 고려하지 않는 것이다. 어차피 홀수인 경우는 항상 0가지 경우의 수만 존재하기 때문에 이들까지 모두 고려해서 배열을 선언해줄 필요가 없다. 즉 5000의 배열 공간을 2500으로 아~~주 미미하게 줄여줄 수 있다.

먼저 DP 배열을 선언해주자. 우리는 문제 예시에서 n = 4일때까지 경우의 수를 제시했으므로 이 값들을 초기화해서 넣어주자. 이때 홀수는 아예 배제하므로 모든 값을 순차적으로 넣어줄 수 있다.

// n=0, n=2, n=4 일때의 경우의 수
// 짝수인 경우만 경우의 수가 존재하므로 홀수는 배제한다
// 따라서 n=0일땐 index[0], n=2일떈 index[1] ... 로 접근한다
const dp = [0, 3, 11];
// 위 주석에서 설명하듯이 index는 n을 2로 나눈 값이다.
const idx = n >> 1;

// n이 짝수가 아니라면 바로 0을 리턴한다.
// 따라서 우리는 dp 배열에 홀수인 경우를 고려하지 않아도 된다.
if(n % 2) return 0;
// 인덱스가 3보다 작은 경우, 즉 0, 1, 2인 경우에는
// 이미 dp 배열에 그 값이 초기화 되어있으므로 바로 리턴
// 사실 생략해도 문제는 없다.
if(idx < 3) return dp[idx];

홀수인 경우를 배제했으므로 반복문을 1씩 증가시키면서 편하게 접근할 수 있다. 만약 홀수를 배제하지 않았다면 2씩 증가시키면서 짝수인 경우만 골라 점화식을 적용했어야 했을 것이다. (거듭 말하지만 정말 이렇게 해도 상관없다!)

// 문제 제한조건에 의한 MOD 값 선언
const MOD = 1000000007;

// idx=3 부터는 dp 배열에 값이 들어있지 않으므로
// 이 값부터 반복문을 돌려주자.
// 범위는 위에서 구한 idx까지 돌리면 된다.
for(let i = 3; i <= idx; i++) {
  // 여기서 3은 dp[1], 즉 n=2 일때의 값과 같다.
  // dp[1]로 선언해도 상관없다.
  // 2는 n=x 일때, x에서 구성할 수 있는 새로운 패턴 2가지이다.
  dp[i] = dp[i-1] * 3 + 2;
  
  // dp[j]는 n=x 일때, (x-2) ~ (2) 까지의 범위이다.
  // 위에서의 첫 연산을 제외하면 각각 이전에 구한 조합은
  // 모두 새로운 패턴인 2가지와 곱해지는 것을 위에서 살펴보았다.
  // i일때 연산은 위에서 2를 더해줌으로 미리 수행했기에
  // i-1 범위까지 반복해주도록 하자.
  for(let j = 1; j < i-1; j++) {
    dp[i] += dp[j] * 2;
  }
  
  // 연산 후에 꼭 MOD 값을 적용해서 저장해주자!
  dp[i] %= MOD;
}

return dp[idx];

5) 전체코드

코드로 보면 길이도 짧고 풀고나면 이해가 가지만, 그 전에 규칙을 찾아내기 까다로운 문제였다. 1줄이 늘어났을 뿐인데 Lv.3 문제와 달리 난이도가 확 뛴 것을 체감할 수 있었다. 이전에 포스팅한 도둑질 문제와는 달리 Lv.4의 무서움을 보여주는 문제라는 생각이 든다. 주석을 제외한 전체코드는 다음과 같다.

const MOD = 1000000007;

function solution (n) {
  const dp = [0, 3, 11];
  const idx = n >> 1;
  
  if(n % 2) return 0;
  if(idx < 3) return dp[idx];
  
  for(let i = 3; i <= idx; i++) {
    dp[i] = dp[i-1] * 3 + 2;
    
    for(let j = 1; j < i-1; j++) {
      dp[i] += dp[j] * 2;
    }
    
    dp[i] %= MOD;
  }
  
  return dp[idx];
}

출처

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