Categories(74)
-
백준 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 -
백준 1943번, 동전 분배 풀이
문제 백준 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]..
2021.01.11 -
백준 1823번, 수확 풀이
문제 백준 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..
2021.01.09 -
백준 1939번, 중량제한 풀이
문제 백준 1939번 풀이 옮길 수 있는 물건의 중량은 이어진 다리의 가중치 중 최솟값이 됩니다. 그러므로 가중치가 큰 간선(다리)을 이어주면서 공장끼리 이동 가능한지 확인하면 됩니다. 이 과정은 유사 크루스칼 알고리즘(Union-Find)을 돌리는 것으로 해결할 수 있습니다. 소스코드 #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; typ..
2021.01.07 -
백준 2170번, 선 긋기 풀이
문제 백준 2170번 풀이 수직선 상에 테스트 케이스를 나타내봅시다. 현재 선이 그이고 있는가? 그이지 않고 있는가?를 생각해보며 문제를 풀어주면 쉽게 풀 수 있습니다. 선이 그이고 있는가 없는가 는 긋기 시작하면 1을 증가시켜주고, 긋는 것을 멈출 때 1 감소시켜주는 변수 하나로 관리할 수 있습니다. 주석으로 설명을 대체합니다. 소스코드 #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; int main() { io..
2020.12.30 -
백준 4913번, 페르마의 크리스마스 정리 풀이
문제 백준 4913번 풀이 구간에 해당하는 소수를 빠르게 구하기 위해서, 구간 $[1, 100,000,000]$에 해당하는 모든 소수를 에라토스테네스의 체를 사용하여 구해줍니다. 해당 구간에 소수를 순서대로 넣으면, 정렬된 상태이기 때문에 이분 탐색을 사용할 수 있습니다. 문제 입력에서 주어지는 $[L, U]$에서 $upper(U) - lower(L) $한 수가 소수의 개수가 되겠네요. 비슷하게 제곱수의 합으로 나타낼 수 있는 수도 위처럼 구할 수 있습니다. 에라토스테네스의 체로 소수($p$)를 구할 때, $(p-1)mod4 = 0$을 만족하는 경우만 따로 관리해주면서, 위처럼 이분 탐색을 사용하여 풀 수 있습니다. 다만, $1^1 + 1^1 = 2$가 되는 "짝수인 소수 2"를 따로 고려해야 합니다. ..
2020.12.26