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

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

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

문제 백준 4913번 풀이 구간에 해당하는 소수를 빠르게 구하기 위해서, 구간 $[1, 100,000,000]$에 해당하는 모든 소수를 에라토스테네스의 체를 사용하여 구해줍니다. 해당 구간에 소수를 순서대로 넣으면, 정렬된 상태이기 때문에 이분 탐색을 사용할 수 있습니다. 문제 입력에서 주어지는 $[L, U]$에서 $upper(U) - lower(L) $한 수가 소수의 개수가 되겠네요. 비슷하게 제곱수의 합으로 나타낼 수 있는 수도 위처럼 구할 수 있습니다. 에라토스테네스의 체로 소수($p$)를 구할 때, $(p-1)mod4 = 0$을 만족하는 경우만 따로 관리해주면서, 위처럼 이분 탐색을 사용하여 풀 수 있습니다. 다만, $1^1 + 1^1 = 2$가 되는 "짝수인 소수 2"를 따로 고려해야 합니다. ..

문제 백준 14621번 풀이 빨간색 파란색을 잇는 간선을 제외하고 모두 제거합니다. 남은 간선을 가지고 정점을 모두 연결시킬 수 있는 MST (최소 스패닝 트리)를 만들면 됩니다. 정렬하는데 $ O(MlogM) $, 연결하는데도 $ O(MlogM) $이 걸리니 시간 복잡도 $O(MlogM)$에 해결할 수 있습니다. MST를 구하는 방법 (백준 1197번, 최소 스패닝 트리(MST)를 구하는 크루스칼 알고리즘) 소스코드 #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 ..