본문 바로가기

백준189

백준 12865 c++ "평범한 배낭" -PlusUltraCode- https://www.acmicpc.net/problem/12865       [필자 사고]Dp문제이다.Dp문제에서 핵심은 Dp를 어떻게 정의하느냐에 있다고 생각한다. 필자는 Dp[i][k] 라고 선언했고 k는 무게를 의미하며 i는 가방의 종류를 의미한다. Dp값은 최대 가치를 의미한다.  max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])이 코드가 핵심이라고 생각한다. 현재의 가방의 최대치를 구하기 위해 먼저 해당 가방의 무게가 k를 넘지 않아야 된다. 다음으로 생각할 것은 현재 가방에 넣은 물건들의  가치 최대치이다. 1. 만약 해당 가방의 무게가 k보다 작은경우에서      이전 Dp[i-1][j] 의 가치가 높은지 아니면 Dp[i-1][j-W[i]]+V[i] 높은지 .. 2024. 5. 9.
백준 c++2749 "피보나치 수 3" -PlusUltraCode- https://www.acmicpc.net/problem/2749       [필자사고]https://www.acmicpc.net/problem/9471  이 문제는 피사노 주기를 알면 쉽게 풀 수 있는 문제이다. 피사노 주기의 특징은 k(10n) = 15×10(n-1) 와 같은 특징이 있따. 예를들어 1000000으로 나눠야 되는 상황이 있으면 k(10^6) = 15x10(10^5) 의 공식이 성립하여 k의 값은 1500000가 된다. 즉 100만으로 나누게 될 경우 15만마다 주기가 생긴다는 점이다. 이 문제의 N의 값은 매우 크기 때문에 모든 값을 다 담게 되면 메모리 초과가 생길것이다. 여기서 핵심은 15만 마다 주기가 반복되므로 15만의 크기의 배열만 확인하면 문제를 쉽게 해결할 수 있따. [소.. 2024. 5. 8.
백준 c++ 2748 "피보나치 수 2" -PlusUltraCode- https://www.acmicpc.net/problem/2748       [필자 사고]이 문제는 문제에 점화식이 써져 있어 다이나믹 프로그래밍 알고리즘을 짜기 수월했다. 다만 한가지 조심해야 되는 점은 자료형의 크기이다. int형으로 자료형을 선언하게 되면 오버플로우가 발생하여 원하는 값이 소실되는 문제가 생긴다. long형으로 바꾸기 혹은 안전하게 long long으로 해결해도 된다.  Fn = Fn-1 + Fn-2 (n ≥ 2)  [소스 코드]#include #include using namespace std;int N;vector Dp;void Input() { cin >> N; Dp.resize(92); Dp[0] = 0; Dp[1] = 1; Dp[2] = 1;}void Solve() { fo.. 2024. 5. 8.
백준 9461 c++ "파도반 수열" -PlusUltraCode- https://www.acmicpc.net/problem/9461      [필자 사고] 이 문제는 이전 값이 영향을 주는 다이나믹 프로그래밍이다. 오른쪽 그림을 보면서 d[11] 까지 직접 손으로 구해보면 규칙성을 금방 찾을 수 있다. 해당 문제의 점화식은 아래와 같다. d[i] = d[i-5] + d[i-1]  단 (i>=6) 이다. 1~5까지의 값은 직접 입력해주고 나머지 범위들을 계산해 주면된다. 또한 index 100까지 가면 int의 범위가 초과되기 때문에 반드시 long 이상의 자료형으로 배열을 초기화 해줘야 된다.  [소스 코드] #include #include using namespace std;int T;vector arr;vector Dp;void Input() { cin >> T; .. 2024. 5. 7.

티스토리툴바