프로그래머스 레벨2 문제이다.
문제요약
효진이는 점프를 1칸 혹은 2칸 할수 있다. 임의의 숫자가 주어질때 뛸수있는 경우의 수를 리턴하면된다.
내가 푼 풀이
처음 문제를 보자마자 완전탐색이구나 라고 생각을 했다.
특히 1234567을 나눈 나머지를 리턴하는 함수 라고 적혀있어서 딱봐도 재귀함수를
활용해야 하구나 라고 생각하게 되었다.
재귀함수를 만들기로 하고 조건들을 설정해봤다. 재귀함수를 적용해서 문제를 풀려고
꼬박 2일이 걸렸는데 문제를 풀지 못하였다.
재귀함수를 만들고 조건식 n과 같을 경우 리턴, 그리고 +2일 경우 +1일 경우 +2했을 경우 n과 같은가? +1 했을 경우 n과 같을까
조건들을 하나씩 추가해봤다. 처음에는 풀리는듯 싶더니 안 풀렸다.
이 때문에 조금만 더하면 풀수 있지 않을까? 조건식들을 수정해가면서 욕심을 내었던것 같다. 조건 값이 커질수록 하나씩 대입해보는게 너무 힘들어져서 결국 해답을 찾아보자 라고 생각을 하게 되었다. 해설을 찾아보니 피보나치 수열을 사용하면 되었다.
피보나치 수열
이전에도 피보나치 수열에 대해 공부했었는데 오래간만에 문제를 푸니 까먹었었다.
찾아보니 알고리즘 초보들은 재귀함수를 이용해서 문제를 푸려고 한다고한다. (나다..)
하지만 재귀함수를 돌리면 돌릴수록 시스템상 과부하가 온다고 한다. 했던 식을들 계속 반복해서 알고리즘을 수행하니 큐 스텍에도 무리가 가기 때문이다.
조건을 잘보면 1,1,3,5,8 이런식으로 배열이 진행되는데 이것이 피보나치수열이다.
쭉 공부하다보니 경우의 수를 구하는데 이전 경우의수(n-1,n-2….) 이렇게 과거에
작업한 내용들을 다시 사용하면 피보나치 수열이구나 라고 해석해버렸다.
해설에 쓴 분들도 그렇고 몇번의 조건을 하다보면 이전 조건들의 식들을 가져다 쓰면
피보나치 수열이라고 한다.
여기 문제를 봐도 그렇다. 계단으로 설명한게 쉽게 이해가 되었는데
계단을 한칸 혹은 두칸 올라갈 경우의 수를 구할때 미리 끝에서 1칸 혹은 2칸을 빼고
나머지에서 경우의 수를 구하면 된다. 이때 1칸 2칸빼고 나머지의 경우에수도
1칸을 올라갈지 2칸을 올라갈지 이전의 경우의수를 계속 사용하게된다.
말로 설명하기는 어렵지만 계단으로 설명해준 글을 읽었을때 이해는 완벽히 된것 같다.
나만의 생각으로 정리를 해보면 이전의 경우의수를 끌고와서 현제의 경우에수에 사용해야 한다면 피보나치 수열을 쓰는게 맞는것 같다.
피보나치 수열에 대해 공부하고 이전에 풀었던 식들을 쭉 다시 삭제하고 문제를 풀었다.
function solution(n) {
const dp = new Array(n+1).fill(0)
dp[0]=1;
dp[1]=1;
for(let i=2;i<n+1;i++){
dp[i]=(dp[i-2]+dp[i-1])%1234567
}
return dp[n];
}
일단 배열들을 만든다. 수열이니 배열들을 만들어야 한다.
n의 개수만큼 배열을 만들고 0으로 채워준다.
그리고 피보나치 수열은 0번째와 1번째값은 1,1로 고정이니
처음에 고정을 해준다.
2부터 for문을 돌때 이전 값들을 더해가면서 풀면된다. 다른 문제에서는 100007을 나누라고 하던데 이 문제에서는 1234567을 나누라고 하니 식을 1234567 나눈 나머지로 설정해준다.
그리고 원하는 수열의 값을 리턴해주면된다.
다른사람의 풀이
나머지 푼들도 피보나치 수열을 적용해서 풀었다.
오늘도 마무리
