링크
https://school.programmers.co.kr/learn/courses/30/lessons/12914
문제
멀리 뛰기를 하는데 한 번에 1칸 혹은 2칸 씩 이동이 가능하다. n개의 칸이 주어질 때, 이동할 수 있는 경우의 수는 모두 몇 가지인가?
예제로 이해
칸이 4칸 일 때 이동할 수 있는 경우의 수는 다음과 같다.
(1칸, 1칸, 1칸, 1칸)
(1칸, 1칸, 2칸)
(1칸, 2칸, 1칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
n = 4일 때, 총 경우의 수는 5이다.
이 문제는 n의 값에 따라 경우의 수가 몇이 나오는지 먼저 생각해본다.
n = 1 => 1
n = 2 => 2
n = 3 => 3
n = 4 => 5
n = 5 => 8
n = 6 => 13
n = 7 => 21 ...
차례대로 경우의 수를 구하고 자세히 보면 피보나치 수열에 관한 공식이 문제에 적용됨을 알 수 있다. 따라서 이 문제는 피보나치 수열에 대해 구하는 방식으로 변경하여 풀면 쉽게 풀 수 있다.
코드
function solution(n) {
let arr = [1, 1, ...new Array(n - 1).fill(0)]
for(let i = 2; i <= n; i++) {
arr[i] = (arr[i-1] + arr[i-2]) % 1234567
}
return arr[n]
}코드 풀이
피보나치 수열을 계산하는 방법에는 반복문을 돌려서 풀이하는 방법과 재귀함수를 호출하여 문제를 푸는 방식이 있는데 프로그래머스에서 재귀함수로 호출하는 방식으로 문제를 풀이하면 스택오버플로우가 발생하기 때문에 반복문으로 문제를 풀어준다.
처음에는 주어지는 n의 값으로 빈 배열을 만들어주는데 0번째와 1번째의 값은 직접 정해주고 나머지는 0으로 채워 빈 배열을 만들어준다.
이후에 반복문을 진행하며 피보나치 수열을 구하는 방식으로 배열의 빈 공간을 채워나간다. (피보나치 수열에 의하면 자기 자신의 앞 두 개의 합이 자기 자신이 된다.)
