본문 바로가기

프로그래머스/DP

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

반응형

1. 문제

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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
반응형