본문 바로가기

백준154

백준 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.
백준 c++ 11053 "가장 긴 증가하는 부분 수열" -PlusUltraCode- https://www.acmicpc.net/problem/11053       [필자 사고] 처음 문제를 보고 있을 때는 완전탐색으로 문제를 풀어 나갔다. 다만 문제가 틀리고 채점 계시판에 있는 반례를 본 후 완전탐색이 아닌 Dp로 풀기로 방향을 바꿨다. 기존 알고 있던 dp는 처음부터 차례대로 증가하는 형태로 쌓아가는 느낌이 많았다. 이 문제는 증가는 하지만 index가 작은 값들을 수시로 검사하는 형태로 쌓아가는 방식이다. dp[i] = max(dp[i], dp[k]+1) 단 i>k  이 사고만 할 수 있으면 문제를 쉽게 풀 수 있다. 다른 후기들을 찾아보니 이 문제는 LIS의 기본 문제라한다. 기본 개념이 들어간 문제이니 기억해야 겠다. [소스 코드]#include#include #include #.. 2024. 5. 1.

티스토리툴바