반응형
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
반응형
'프로그래머스 > DP' 카테고리의 다른 글
[DP] 프로그래머스 '스티커 모으기(2)' - js (0) | 2023.05.11 |
---|---|
[DP] 프로그래머스 '숫자 변환하기' - js (0) | 2023.04.26 |
[DP] 프로그래머스 '땅따먹기' - js (0) | 2023.04.11 |
[피보나치] 프로그래머스 '멀리뛰기' - js (0) | 2022.10.20 |