문제 백준 13398번 풀이 그냥 연속한 수열에서 최댓값을 구하는 점화식은 $ dp[i] = max(dp[i] + arr[i], 0) $이라는 것을 알고 있습니다. ( ... ⓐ ) 여기 다른 dp 배열을 하나 더 만들어, 수를 한번 제거하였을 때의 최댓값도 같이 관리해줍니다. ( ... ⓑ ) 그러면, ⓐ의 DP 배열을 $ A $, ⓑ의 DP 배열을 $ B $라고 하면, $ A $는 위 점화식으로 쉽게 채워줄 수 있습니다. $ B = max(A[i - 1], B[i - 1] + arr[i]) $라는 점화식으로 나타낼 수 있습니다. $ A_i $까지 더한 합에서 $ i $만 제하는 경우 또는 $ B_i $에서(이미 한번 뺀 경우) 현재 값을 더해준 경우로 두 가지로 나뉘기 때문에 위와 같은 점화식이 나옵..

문제 백준 2201번 풀이 길이가 $ 1, 2, 3, 4, 5 $인 이친수들을 모두 적어보겠습니다. $ 1 $ $ 10 $ $ 100, 101 $ $ 1000, 1001, 1010 $ $ 10000, 10001, 10010, 10100, 10101 $ 이며 각각의 개수는 $ 1, 1, 2, 3, 5 $와 같습니다. 대충 규칙이 피보나치 수열과 같다는 것을 볼 수 있습니다. 길이가 $K$인 이친수의 개수가 피보나치 수열의 원소와 같다는 믿음을 가지면 아래 문제를 푸는 것으로 바꿀 수 있습니다. $N$번째 이친수의 길이는 몇인가? 이는 피보나치 수열을 한번 돌리면 길이를 구할 수 있습니다. 다음은, 길이가 $ K ( K \geq 2) $인 경우 이친수는 "항상" 앞이 10으로 시작합니다. (이친수의 시작은 ..

문제 백준 1943번 풀이 $ dp[i] = i $원일 때 가진 동전으로 $i$원으로 만들 수 있으면 1, 없으면 0으로 점화식을 세워줍니다. 동전의 합이 $ sum $일 때, 두 명에게 같은 돈으로 나눌 수 있는지 없는지는 $dp[sum/2]$가 1인지 확인하면 됩니다. $sum$이 홀수인 경우 어떤 식으로 나눠도 홀/짝, 짝/홀로 나눠지므로 두 명에게 같은 돈으로 나눌 수 없습니다. 구하고자 하는 것은 $sum/2$의 값으로 문제에서 $sum$의 범위가 $100,000$으로 주어졌으므로 DP table의 크기는 $ 50,000 (+1) $으로 잡아야 합니다. DP table을 채우기 위해서 $50,000$부터 $a$까지 내려가면서 $dp[i - a]$의 값이 1이라면 $dp[i],\ dp[i + a]..

문제 백준 1823번 풀이 $ dp[i][j] = $ 왼쪽에서 $ i $번째, 오른쪽에서 $ j $번째를 뽑을 차례일 때의 최대 이익으로 점화식을 세우면 풀 수 있습니다. (단, $i < j$) 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vpii; typedef vector vpll; typedef unordered_map mpii; int dp[2001][2001]; in..

문제 백준 20312번 풀이 CPU $ i + 1$번째의 $ j $행은 CPU $ i $번째 $ j $행의 $ m_{i} $배 입니다. 따라서, $ i + 1 $번째 CPU 행의 합 = ($ i $번째 CPU 행의 합 + 1) * $ m_{i} $이 됩니다. 이전 행의 값을 계산해두면, 하나를 구할 때 $ O(1) $이므로, 모두 다 구해주는데 $ O(N) $이 걸리겠네요. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef v..

문제 백준 2662번 풀이 전형적인 DP 문제입니다. $ dp[i][cost] = "$ $ i $번째 회사까지 $ cost $원을 사용했을 때 최대 이익금" 이라고 점화식을 세웁니다. 회사 하나를 늘릴 때마다 어떤 cost ($ 1 \leq cost \leq N $)를 고정시키고, prev ($ 1 \leq prev \leq cost $) 를 순회해주며 DP Table을 채워줍시다. 역추적은 $ dp[i][cost] $가 최댓값을 가질 때의 $ prev $의 값을 저장해두면서 $ dp[i - 1][prev] $... 이런식으로 역추적해나가면 됩니다. 시간 복잡도는 $ O(N^3) $이 됩니다. 소스코드 #include using namespace std; typedef long long ll; typed..