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

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

문제 백준 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) $이 걸립니다. 쿼리..

문제 한국정보올림피아드 2013년 고등부 1번 백준 8983번 풀이 사대의 위치와 동물의 위치 간의 거리는 x좌표의 차이와 동물의 y좌표를 더한 값입니다. 또한, 사대는 x축 위에 있기 때문에 y좌표는 어느 사대를 선택하던 변하지 않습니다. 즉, 동물과 가장 가까운 사대를 구하려면 x좌표의 차이가 최소가 되는 사대를 찾으면 됩니다. 동물의 수와 사냥꾼의 수가 최대 100,000이므로 각 동물에 대한 최적의 위치에 있는 사대를 찾을 때 완전 탐색을 하면 TLE가 납니다. 가장 가까운 사대를 찾기 위해 동물의 x 좌표에 대한 이분 탐색을 해봅시다. 이 때, lower_bound를 사용하는 경우 사대의 후보가 2개가 나옵니다. 이 경우에는 lower_bound로 선택된 사대가 정답입니다. 하지만 아래의 경우에..

문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다. ​1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다. 시간 복잡도는 $ O(N^3) $ 가 됩니다. ​2번은 투포인터 또는 분할 정복을 사용하면 됩니다. 비슷한 문제: https://www.acmicpc.net/problem/2003​​ 3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다. 그리고 대부분이 못 푼 것 같습니다. TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsig..