백준/동적프로그래밍15 백준 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. 백준 2156 c++ "포도주 시식" -PlusUltraCode- https://www.acmicpc.net/problem/2156 [필자 사고]동적프로그래밍 문제이다. 필자는 개인적으로 동적프로그래밍을 만나면 직접 손으로 풀어본다. 몇개의 사례를 직접 손으로 풀어봐야 점화식이 만들기가 쉬워진다. 이 문제를 손으로 푼 결과 특정 인덱스에 해당하는 값의 최대값을 구하기 위해서는 1. 3칸 전Dp + Arr[i-1] + Arr[i]인 경우2. 2칸전 Dp + Arr[i]3. 1칸전 Dp[i-1] 인 3가지 경우중 최대값을 갱신해주면 풀 수 있게 된다. Dp[i] = max(Dp[i-3]+ Arr[i-1] + Arr[i] , Dp[i-2] + Arr[i] , Dp[i-1]); 1번 해설 :현재 idx와 이전 idx를 선택하게되면 연속으로 전전idx를 선택 못하.. 2024. 5. 6. 백준 c++ 11727 "2×n 타일링 2" -PlusUltraCode- https://www.acmicpc.net/problem/11727 [필자 사고] 동적프로그래밍이다. 필자는 dp[i]를 다음과 같이 정의하였다. dp[i] = dp[i-2]*2 + dp[i-1]; dp[i-2]의 의미는 현재 플록에서 2cm를 뺀 그동안 쌓아온 블록의 수를 의미한다. *2를 한 이유는 2cm간의 빈 공간을 어떠한 타일로 채울 것인지에 대한 의미이다. 1x2 인 형태인 타일을 위 아래로 놓는 경우의 수와 2X2 타일 한개를 넣는 경우의 수 총 2개라고 생각하여 곱셈 연산을 해주었다. 여기서 중요한 점은 2x1 타일 즉 위 아래로 기다란 타일의 경우의 수를 뺀 이유는 dp[i-1] 때문이다. dp[i-1]은 위와 같이 1cm의 빈 곤강을 의미하므로 자동적으로 하나의 경우의.. 2024. 5. 2. 이전 1 2 3 4 다음
