프로그래머스 LEVEL 2(3 x n 타일링)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-12-28

  • 해결 방법 :

    • n이 홀수일 경우는 타일링 불가능
    • n이 짝수일 경우 점화식에 따라 계산 가능
      • f(n) = f(n - 2) x 4 - f(n - 4)
        • n === 2일 경우, 3
        • n === 4일 경우, 11
        • n === 6일 경우, 41
        • n === 8일 경우, 153
    • 따라서 n이 2와 4일 경우 early return
    • n이 6 이상일 경우 2씩 증가시키며 값 계산
      • 이 때 경우의 수가 커질 경우를 대비해 1000000007로 나눈 나머지를 반환하되,
      • 점화식 f(n) = f(n - 2) x 4 - f(n - 4)을 계산할 때 f(n - 2) x 4가 f(n - 4)보다 더 작은 경우 음수가 나오므로 1000000007을 더한 후 1000000007로 나눈 나머지 반환

  • 회고 :

    • 처음에 n이 2, 4, 6, 8, … 의 개수를 구할 때 각 n에서 새로 추가되는 타일을 생각하지 못했다.
    • 예를 들어 n === 6일 경우, 이전과 대비해
      • |==|
      • -–
      • 과 같은 경우가 2개씩 추가된다.

  • 코드

    function solution(n) {
  if (n === 2) return 3;
  if (n === 4) return 11;

  let count1 = 3;
  let count2 = 11;
  let temp = 0;

  for (let i = 6; i <= n; i += 2) {
    temp = count1 % 1000000007;
    count1 = count2 % 1000000007;
    count2 = (count1 * 4 - temp + 1000000007) % 1000000007;
  }

  return count2;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges