[프로그래머스] 아방가르드 타일링

문제

문제 링크

정우는 예술적 감각이 뛰어난 타일공입니다. 그는 단순한 타일을 활용하여 불규칙하면서도 화려하게 타일링을 하곤 합니다.

어느 날 정우는 가로 길이 n, 세로 길이 3 인 판을 타일링하는 의뢰를 맡았습니다. 아방가르드한 디자인 영감이 떠오른 정우는 다음과 같은 두 가지 종류의 타일로 타일링을 하기로 결정했습니다.

각 타일은 90도씩 회전할 수 있으며 타일의 개수는 제한이 없습니다.

n이 주어졌을 때, 이 두 가지 종류의 타일로 n x 3 크기의 판을 타일링하는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

• 1 ≤ n ≤ 100,000
• 결과는 매우 클 수 있으므로 1,000,000,007 로 나눈 나머지를 return합니다.

---

입출력 예

n	result
2	3
3	10

---

입출력 예 설명

입출력 예 #1

위 그림과 같이 3 가지 방법으로 타일링할 수 있습니다.

입출력 예 #2

위 그림과 같이 10 가지 방법으로 타일링할 수 있습니다.

풀이

힌트가 없었다면 풀지 못했을 문제
처음에는 n=1,n=2,n=3일때만 고유의 패턴이 있다고 생각해서 일반항을
S(n) = S(n-1) + 2*S(n-2) + 5*S(n-5)로 놓고 풀었더니 계속 실패했다.
답답해서 질문글을 찾아보니 b=4 이후에도 가로에 1x3 타일을 추가하는 방식으로 3을 주기로 고유한 패턴이 있음을 알 수 있었다. 힌트 링크
n=1일때 1개
n=2일때 2개
n=3일떄 5개
n=4+3(n-1)일때 2개
n=5+3(n-1)일때 2개
n=6+3(n-1)일때 4개
따라서 일반항은

• S(n) = S(n-1) + 2*S(n-2) + 5*S(n-3) + 2*S(n-4) + 2*S(n-5) + 4*S(n-6) + 2*S(n-7) + 2*S(n-8) + 4*S(n-9) + ...

3을 주기로 반복되므로

• S(n) - S(n-3) = S(n-1) + 2*S(n-2) + 5*S(n-3) + S(n-4) - S(n-6)
• S(n) = S(n-1) + 2*S(n-2) + 6*S(n-3) + S(n-4) - S(n-6) 이다.

Top Down은 시간초과라서 Bottom Up 방식으로 해결했다.
이때 n이 커지면 int형의 범위를 초과하므로 배열에 들어가는 모든 값을 제한해줘야한다.
문제에서 요구하는 답은 nx3을 타일링 하는 방법을 1,000,000,007로 나눈 나머지이므로.
모듈러 분배법칙에 따라 배열에 들어가는 수를 제한해줬다.

• (a+b) mod c = ((a mod c) + (b mod c)) mod c

코드

function solution(n) {
  const arr = [0, 1, 3, 10, 23, 62, 170];
  if (n < 7) {
    return arr[n];
  }
  const mod = 1_000_000_007;
  const result = arr.concat(Array.from({ length: n - 6 }, () => 0));
  for (let i = 7; i < n + 1; i++) {
    //모듈러 분배법칙, 메모리 초과 방지
    const temp =
      ((result[i - 1] % mod) +
        ((2 * result[i - 2]) % mod) +
        ((6 * result[i - 3]) % mod) +
        (result[i - 4] % mod) -
        (result[i - 6] % mod)) %
      mod;
    // 음수체크
    result[i] = temp > 0 ? temp : temp + mod;
  }
  return result[n];
}

Top Down 방식

function solution(n) {
  const arr = [0, 1, 3, 10, 23, 62, 170];
  if (n < 7) {
    return arr[n];
  }
  const mod = 1_000_000_007;
  return (
    ((solution(n - 1) % mod) +
      ((2 * solution(n - 2)) % mod) +
      ((6 * solution(n - 3)) % mod) +
      (solution(n - 4) % mod) -
      (solution(n - 6) % mod)) %
    mod
  );
}