반응형
1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=javascript
2. 설명
이 문제는 피보나치 형태의 규칙을 따른다.
1칸 움직이는 방법 => 1
2칸 움직이는 방법 =>2
3칸 움직이는 방법 =>3
4칸 움직이는 방법 =>5
5칸 움직이는 방법 =>8
fib(n) = fib(n-1) + fib(n-2) 의 형태와 동일하다!
하지만 이 문제에서 0칸은 고려하지 않으니, 가독성을 위해 배열에 처음부터 [0,1,2]를 할당해주고 시작한다. 아니면 기존의 피보나치처럼 [0,1,1]을 할당해준 후 n+1의 값을 리턴해줘도 된다.
오버플로우를 방지하기 위해 값을 1234567로 나눈 나머지 자체를 집어넣어준다. 마지막으로 dp의 n번째 인덱스를 1234567로 나눈 나머지를 리턴해주면 정수 오버플로우 문제 없이 통과된다!
3. 코드
정답 코드)
function solution(n) {
let dp=[0,1,2];
for(let i=3;i<=n;i++){
dp[i] = (dp[i-1]+dp[i-2])% 1234567;
}
return dp[n]%1234567;
}
// 또는
function solution(n) {
let df = [0,1,1];
for(let i=3;i<=n+1;i++){
df[i] = (df[i-1] + df[i-2]) % 1234567;
}
return df[n+1];
}
처음에 작성한 코드)
function solution(n) {
if(n<=2) return n;
return (solution(n-1) + solution(n-2)) % 1234567;
}
반응형
'프로그래머스 > DP' 카테고리의 다른 글
[DP] 프로그래머스 '스티커 모으기(2)' - js (0) | 2023.05.11 |
---|---|
[DP] 프로그래머스 '숫자 변환하기' - js (0) | 2023.04.26 |
[피보나치] 프로그래머스 '2xn 타일링' - js (0) | 2023.04.22 |
[DP] 프로그래머스 '땅따먹기' - js (0) | 2023.04.11 |