문제 BOJ 1253 풀이 $ i $번째 수를 만들기 위해 $ j $번째 수와 $ k $번째수를 구한다고 가정합시다. 순서쌍 $ (i, j) $를 모두 구하면 경우의 수가 $ {n}C_{r} $이 됩니다. 이 순서쌍에서 남은 $ k = (i - j) $를 이분 탐색을 사용하여 log 복잡도로 구해봅시다. 그리고, 이분 탐색을 사용하여 구한 $ k $가 $ i $ 혹은 $ j $와 겹치는 경우를 확인하여 추가로 탐색해야 합니다. 전체 시간복잡도가 $ O(N^2logN) $이 되므로 시간 내에 해결할 수 있습니다. 이 문제에서 유의해야할 점은 $ A_{i} $와 $ A_{j} $가 같더라도 서로 다른 수로 취급합니다. 문제의 질문에서 여러 테스트 케이스를 정리해두었으니 직접 푸는데 도움이 되길 바랍니다. 6..

문제 백준 1240번 풀이 나가는 간선의 개수가 $ N - 1 $이고, 정점의 개수가 $ N $이므로 SPFA를 통해 구현하는 경우 최악의 시간 복잡도는 $ O(N^2) $이 됩니다. 테스트케이스의 개수가 $ M (\leq 1000) $이므로 최악의 경우 $ O(MN^2) $이 되어 TLE가 날 것 같이 생겼습니다. 하지만, 같은 그래프에 대해서 그러한 최악의 경우가 $ M $개가 되는 경우는 없다는 믿음을 가지고 SPFA를 사용하여 구현해봅시다. 16ms에 AC가 나오는 것을 볼 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pai..

문제 백준 2110번 풀이 서로의 간격을 $ mid $ 이내로 C개의 공유기를 모두 배정할 수 있는가? 라는 결정 문제로 두었을 때, NNN...YYY로 단조롭게 나올테니 파라메트릭 서치를 사용할 수 있습니다. 발상과 구현에서 살짝 어렵다고 생각합니다. 실버 1~2 문제는 아니라고 생각합니다. 소스코드 #include 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() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(..

문제 백준 1083번 풀이 그리디 문제입니다. $ i $를 $ 1 $부터 $ N $까지 순서대로 순회하면서, $ i $번째에 가능한 수 중 가장 큰 수를 넣어야 합니다. 모든 $ i ( 1 \leq i \leq N) $에 대하여 구간 $ [i, min(i + S, N)] $에 속하는 값 중 최댓값을 $ i $번째에 가져다 놓으면 됩니다. ($ S $는 사용한만큼 감소시킴) $ N $의 범위가 50이므로, 막구현해도 TLE가 나지는 않습니다. 다만, 탐색 범위를 한번 더 확인해서 런타임 에러를 주의할 필요는 있습니다. 소스코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.t..

문제 백준 1737번 풀이 기본적인 피보나치 문제도 DP이기 때문에, DP를 사용하는 문제임에는 쉽게 알 수 있습니다. 다만, 소수점 오차 때문에 dp table을 잡기가 조금 애매합니다. 소수점 오차를 줄이기 위해서 $ n $에서 뺄 1의 개수와 $ \pi $의 개수를 기록하여 dp table을 채우면 될 것 같습니다. $ dp[i][j] = f(n - i - \pi j) $라고 두고 재귀 함수로 풀었습니다. (단, $ f $는 Pibonacci 함수) 소스코드 #include using namespace std; typedef unsigned long long ull; ull MOD = 1000000000000000000; ull dp[1001][1001]; long double n; ull solv..

문제 백준 16074번 풀이 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로에서 방문하는 정점 중 최대 높이를 최소화하여야 합니다. $ Q = 1 $이라고 가정하면, 높이가 $ mid $보다 작은 정점들만 사용하여 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로가 있는가 에 대한 결정 문제를 풀어야 합니다. Union-Find 자료구조를 사용하여 $ mid $보다 작은 정점들을 순서대로 합쳐주는 것은 유사 크루스칼 알고리즘을 돌려 결정 문제를 해결할 수 있습니다. 높이 $ H $에 대한 이분 탐색 $ O(log H) $, 총 정점의 개수가 $ MN $이므로 유사 크루스칼 알고리즘을 돌리는데 $ O(MNlogMN) $이 걸립니다. 쿼리..