hades

🥅 문제https://www.acmicpc.net/problem/1003 🔍 설계재귀 함수로 설계할 경우, 시간 초과가 발생할 것이다.  fibonacci(N)을 출력했을 때, 0과 1의 호출 횟수는 fibonacci(N-1)과 fibonacci(N-2)의 0과 1의 호출 횟수와 관련이 있으므로, 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 👊 풀이#include #include #include using namespace std;int t, n;vector> dp(41, {0, 0});int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> t; dp[0].first = 1; dp[1].second = 1; for (int i=..

🥅 문제https://www.acmicpc.net/problem/1463 🔍 설계시간 제한이 0.15초이고, N이 최대 1000000이므로, 보통 1초 당 1억 번의 연산을 하기 때문에 재귀함수를 사용한다면, Ω(N^2)의 시간 복잡도로 시간 제한을 초과한다. N에서 시작하는 것이 아니라, 반대로 1에서 시작하여 문제에서 주어진 연산을 반대로 하여 다이나믹 프로그래밍으로 설계한다면, O(N)으로 해결할 수 있다. 👊 풀이#include #include #include using namespace std;int n, INF = 1e9+7;vector dp(1000001, INF);int main() { cin >> n; dp[1] = 0; for (int i=1; idp[i]는 i로부터 1을 만들기 ..