문제 백준 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..

문제 백준 2737번 풀이 $n$을 $a$부터 $b$까지의 합으로 나타내면 아래와 같습니다. $$ n = a + a + 1 +\ \cdot\cdot\cdot \ + b - 1 + b $$ $a$부터 $b$까지 $k$개를 뽑는다고 하면 첫째항이 $a$이고 끝항이 $a + k - 1$가 되며, 등차가 1입니다. 등차수열의 합 공식에 의해서 $$ n = \frac{k(2a + k - 1)}{2} $$ 로 나타낼 수 있습니다. 식을 정리하면 $$ k^2 + k(2a - 1) - 2n = 0 $$ 으로 나타낼 수 있고, 근의 공식에 의해서 $$ k = \frac{1 - 2a \pm \sqrt{4a^2 - 4a + 1 + 8n}}{2} $$ 이 됩니다. 뽑는 수 $k$를 최대로 하려면, 첫째항 $a$를 $ 1$로 ..

문제 백준 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이 됩니다. $$ ..

문제 백준 1407번 풀이 구간 $[A, B]$를 1씩 증가 시켜보면서 확인하는 방법이 가장 확실하지만, 수의 제한이 무려 $10^{15}$이니 더 빠른 방법을 찾아야 합니다. 우리가 관심 있는 것은 구간 $[A, B]$에서 $2^k$의 배수의 개수입니다. 어떤 수, $k$가 주어졌을 때, 구간 $[A,B]$ 내에서 $k$의 배수의 개수는 $B/k-(A-1)/k$라는 수식을 통해 $O(1)$로 구할 수 있습니다. (단, $A \leq B$) 두번째, $2^{k+1}$의 배수는 모두 $2^k$의 배수입니다. 예를 들면, $32(2^5)$과 같은 수는 $16(2^4)$의 배수임에 동시에 $8, 4, 2, 1$의 배수이기도 합니다. 즉, $2^k$의 배수는 모두 $2^i (i=0,1,...,k)$의 배수라고 ..

문제 백준 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..