[피보나치] 프로그래머스 '2xn 타일링' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12900#qna

프로그래머스

2. 코드

오랜만에 메모이제이션 방식으로 풀어보고 싶어, 해당 코드를 작성했는데 타임아웃이 해결되지 않았다. 이유는 아직 파악하지 못했다.. 아 재귀라서 그런가...? 계속 solution 함수를 불러와서..?

처음 푼 코드) 타임아웃

function solution(n, memo = []) {
    if (n <= 2) return n;
    if (memo[n]) return memo[n] % 1000000007;
    const result = (memo[n]) = (solution(n - 1, memo) % 1000000007 + solution(n - 2, memo) % 1000000007) % 1000000007;
    
    return result;
}

다시 푼 코드)

왠만하면 재귀보단 for문을 사용하는게 좋을 것 같다... DP 방식 꼭 기억하기!

function solution(n) {
  let dp = [0,1,2];
  
  for(let i = 3; i <= n; i++) {
    dp[i] = (dp[i-2] + dp[i-1]) % 1000000007;
  }
  
  return dp[n];
}

 

복기

6/12