Problem Solving(60)
-
백준 2201번, 이친수 찾기 풀이
문제 백준 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으로 시작합니다. (이친수의 시작은 ..
2021.02.05 -
백준 2143번, 두 배열의 합 풀이
문제 백준 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..
2021.01.29 -
백준 2737번, 연속 합 풀이
문제 백준 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$로 ..
2021.01.27 -
백준 2560번, 짚신벌레 풀이
문제 백준 2560번 풀이 문제의 지문에서는 짚신 벌레가 산 날을 기준으로 예시를 보여주었는데, 짚신 벌레가 태어난 날을 기준으로 예제 테스트 케이스를 풀어보겠습니다. 각 표의 번호는 짚신 벌레가 태어난 날입니다. 2번째 날에는 0번째 날(처음 들어있는 짚신벌레)로부터 태어나므로 0 -> 2라고 적었고, 아래 표도 비슷한 방법으로 적었습니다. 위 표에서 $day$일에 태어난 짚신벌레의 수를 $cnt[day]$라고 정의합니다. $day$일 때 얼마의 짚신벌레가 태어나는지, 얼마의 짚신벌레가 죽는지 알아봅시다. $k$일에 태어난 짚신벌레는 $day-k$일만큼 살았다고 표현할 수 있고, 문제에서 주어진 조건에 따라 아래와 같은 부등식을 세울 수 있습니다. $$a \leq day - k \leq b - 1$$ ..
2021.01.26 -
백준 10986번, 나머지 합 풀이
문제 백준 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이 됩니다. $$ ..
2021.01.23 -
백준 1407번, 2로 몇 번 나누어질까 풀이
문제 백준 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)$의 배수라고 ..
2021.01.17