문제 백준 2143번 풀이 $ T = A$의 부분 누적합 + $B$의 부분 누적합으로 둘 수 있으며, $A$의 부분 누적합이 $k$가 되는 경우의 수를 $N^2$에 찾을 수 있습니다. $B$의 부분 누적합 + $k = T$가 되어야 하는데, $k$는 위에서 전처리한 경우의 수만큼 될 수 있습니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef ve..

문제 백준 10986번 풀이 태그는 누적합 문제가 붙어있지만, 저는 수식 정리 연습 문제라고 느꼈습니다. 누적합을 아래와 같이 정의합니다. $$ S(i, j) = \sum_{k=i}^j A[k] $$ (단, $i \leq j$) 한편, $ sum[i] = S(1, i) $의 배열을 만들어두면, 임의의 누적합 $ S(i, j) $에 대하여 $ sum[j] - sum[i - 1] $로 나타낼 수 있으므로 $O(1)$에 구할 수 있습니다. 본격적인 수식 정리를 해보겠습니다. $$ S(i, j) = sum[j] - sum[i - 1] = kM $$ (단, $k$는 자연수) 위 식에서 $M$으로 나눈 나머지를 구해봅시다. * 우변인 $kM$이 항상 $M$의 배수이므로 $M$으로 나눈 나머지는 0이 됩니다. $$ ..

문제 백준 15976번 풀이 문제를 관찰하면, 수열 $ X $의 원소 $ X_{i} $에 곱해지는 수열 $ Y $의 원소들이 연속됨을 알 수 있습니다. $ X_{i} $에 곱해지는 수의 합은 누적합을 사용하여 전처리해두면 빠르게 구할 수 있습니다. 문제는 누적합을 구현할 때 일반적으로 $ sum[i] = i $번째까지 더한 누적합이라고 정의하고 풀게되는데, 이렇게 구현하면 메모리 초과가 발생합니다. 누적합 배열을 $ sum[i] = \{j, value\} $와 같이 두고, 수열 $ Y_{j} $번째 까지 더했을 때 더한 값을 $ value $로 둡시다. 문제에서 인덱스 값의 입력이 오름차순으로 주어진다고 하였으니, 입력 순서대로 $ sum $ 배열을 만드는데, $ O(N) $만 필요합니다. (입력과 함께..

문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..