프로그래머스 2xn 타일링 Javascript

  • Title : 프로그래머스 2xn 타일링 Javascript
  • Date : 2019-11-29
  • Category: 알고리즘 풀이

문제 설명

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

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

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

제한 사항

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

풀이

문제를 보는 순간 규칙이 있을 거 같다는 생각을 했다.
근데 그 규칙 찾는 데 한참 걸렸다.. ㅠ__ㅠ

결론부터 말하자면, 이 문제의 점화식은 DP[N] = DP[N-1][n-2] 다. 그리고 n이 최대 60000 이므로 재귀를 쓰는 것보다 메모이제이션을 이용하는 게 낫다고 판단했다.

아래는 점화식 도출 과정이다.

  • n = 0, 1개
  • n = 1, 1개
  • n = 2, 2개 (DP[1] + DP[0])
  • n = 3, 3개 (DP[2] + DP[1])
  • n = 4, 4개 (DP[3] + DP[2])
  • ....
function solution(n) {
  const memo = Array(n + 1).fill(0);
  memo[0] = 1;
  memo[1] = 1;
  for (let i = 2; i < n + 1; i++) {
    memo[i] = (memo[i - 1] + memo[i - 2]) % 1000000007;
  }
  return memo[n];
}


보노보노

안녕하세요, 보노보노 입니다. ASP 웹 개발로 개발자의 길을 시작했고 현재는 프론트엔드 개발자로 일하고 있습니다. 유저의 행동을 예측하고 최적의 UI/UX를 제공하는 것을 좋아합니다. 최근에는 트위터를 시작했습니다.