백준17175 - 피보나치는 지겨웡~ (DP) JS 본문
반응형
https://www.acmicpc.net/problem/17175
문제는 피보나치 수열을 응용하여, input이 들어왔을 때 피보나치 수열이 몇 번 호출되는지를 묻는다.
먼저 문제에서 제시된 함수를 살펴봐야 하는데,
fibonacci(n)이 호출되고 fibonacci(n-1)과 fibonacci(n-2)이 호출됨을 확인할 수 있다.
(이때 n이 2 이하인 경우는 추가 호출이 없음을 인지해야 한다.)
즉 예를 들면 다음과 같다.
// input === 2
fi(2)
fi(1) fi(0)
// => 총 3번 호출
// input === 3
fi(3)
fi(2) fi(1)
fi(1) fi(0) // 이때 fi(1)와 fi(0)은 fi(2)에서 일어나는 호출
// => 총 5번
// input === 4
fi(4)
fi(3) | fi(2)
fi(2) fi(1) | fi(1) f(0) // 각각 fi(3), fi(2)에서 일어나는 호출
fi(1) fi(0) // fi(2)에서 일어나는 호출
// => 총 10번
// input === 5
fi(5)
fi(4) fi(3)
fi(3) fi(2) | fi(2) fi(1)
fi(2) fi(1) | fi(1) fi(0) | fi(1) fi(0)
fi(1) fi(0)
// => 총 15번
따라서 fibonacci의 배열은 아래처럼 구성된다고 볼 수 있는데,
해당 배열은 dp[i] = dp[i-1] + dp[i-2] + 1 을 만족하므로 해당 식을 점화식으로 수립할 수 있다.
const dp = [1,1,3,5,9,15]
// dp[i] = dp[i-1] + dp[i-2] + 1
소스 코드
const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
.toString().trim()
function solution(data) {
const dp = [1,1,3,5,9,15]
for(let i = 6 ; i <= data ; i ++)
dp[i] = (dp[i-1] + dp[i-2] + 1) % 1000000007
console.log(dp[data])
}
solution(input)
반응형
'개발 > algorithm' 카테고리의 다른 글
백준11048 - 이동하기 (DP) JS (0) | 2023.10.14 |
---|---|
백준1337 - 올바른 배열 JS (0) | 2023.10.12 |
백준13909 - 창문 닫기 JS (0) | 2023.10.09 |
프로그래머스 - Lv.2 2개 이하로 다른 비트 JS (1) | 2023.10.08 |
백준5671 - 호텔 방 번호 (DP) JS (0) | 2023.10.07 |
Comments