이분탐색6 BOJ 26092 https://www.acmicpc.net/problem/26092 26092번: 수학적인 최소 공통 조상 첫째 줄에 정수 $a$와 $b$가 공백으로 구분되어 주어진다. $(1\leq a,b\leq 10^{12})$ www.acmicpc.net 시간복잡도 훈련에 좋은 문제입니다. 관찰 1. \( n \)의 소인수를 모두 구하는데 걸리는 시간은 \(O(\sqrt{n})\) 입니다. 정수 \(a, b\)에 대해 \(n=ab\)라고 표현할 수 있습니다. 일반성을 잃지 않고 \(a\leq b\) 라고 두면, \(n = ab\geq a^2 \) 이므로 \(a\leq \sqrt{n} \) 이 됩니다. 즉, 두 곱으로 쪼갰을 때, 작은 수 \(a \)만 찾으면 나머지 수는 \(n/a \)로 결정됩니다. 관찰 2. 값.. 2022. 12. 25. AtCoder ABC 257 D, E D. https://atcoder.jp/contests/abc257/tasks/abc257_d D - Jumping Takahashi 2 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 시작점을 잘 정해서 조건을 만족하도록 전부 순회할 수 있는지 그 때 최소의 S를 찾는 문제입니다. 시작점을 고정하고, S도 고정시킨 후 각 점에서 다른 모든 점으로 조건을 만족한다면 그래프 위에서 선분으로 연결해줍니다. 이 때, dfs를 쭉 해주고 나면 모든 점을 방문했는지 여부를 O(N)에 알 수 있습니다. 이제 시작점을 선택하는 경우 .. 2022. 9. 8. AtCoder ABC 265 풀이 A. 1개살때 X원, 3개살때 Y원이 들때 N개살때 최소비용을 구하는 문제입니다. 우선, Y가 3X이상이면 그냥 다 1개씩 사면 됩니다. 그 외의 경우엔 3개씩 최대한 묶고 남은걸 1개씩 사주면 됩니다. #include using namespace std; int main() { ios::sync_with_stdio(0), cin.tie(0); int x, y, N; cin >> x >> y >> N; if (y >= 3 * x) { cout n >> m >> t; for (int i = 1; i > a[i]; psum[i + 1] = psum[i] + a[i]; } ll time_limit = t; x[0] = 1; for (int i = 1; i > x[i] >> y[i.. 2022. 8. 25. 백준 25112 / C++ https://www.acmicpc.net/problem/25112 25112번: Single-track railway The first line specifies the number of stations, $n$. In the second line, $n - 1$ numbers are given, corresponding to the initial travel times between the adjacent stations (the $i$-th number is the travel time between stations $i$ and $i + 1$). The third www.acmicpc.net [ 풀이 ] 매번 업데이트하면서 min(S[n]-2*S[i])를 찾아주는 문제이다. 펜윅트리로 업데이트해주.. 2022. 8. 12. 이전 1 2 다음