📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32655 🧐 관찰 및 접근 # 시작 정점에서 각 출구로 갈 수 있는 최단 경로를 구한 후, 열리는 타이밍에 맞춰 나갈 수 있는 최소 시간을 구하자. $KX$초 단위로 출구가 도는게 로테이션 돌고, 이분탐색으로 그 타이밍을 찾은 후 그 블럭에서 나갈 수 있는지, 그 다음블럭에서 나갈 수 있는지 체크하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } vector<ll> dist(N+1, LLONG_MAX); priority_queue<pll, vector<pll>, greater<pll>> pq; dist[1] = 0; pq.push({0, 1}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(dist[cur] < cd) continue; for(auto [nxt, w]: links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1300 🧐 관찰 및 접근 # 나이브하게 계산한다면, 정수가 $10^{10}$개 있으니 아무것도 안된다. 심지어 저장도 불가능하다. 어떤 수 $X$가 주어질 때, $X$보다 작거나 같은 수가 몇개인지는 $O(N)$에 셀 수 있다. 그리고 $X$보다 작거나 같은 수가 $K$개 이상인 수중 가장 작은 $X$가 정답이다. 따라서 파라메트릭 서치를 이용해 $O(N\log{10^9})$정도에 계산하자. 💻 풀이 # 코드 (python): N = int(input()) K = int(input()) def count(X): # 배열에서 X 이하 수의 개수 result = 0 for i in range(1, N+1): result += min(N, X // i) return result ok = N*N ng = 0 # 답의 범위는 [1, N*N]이므로 while ok - ng > 1: mid = (ok + ng) // 2 if count(mid) >= K: ok = mid else: ng = mid print(ok) 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23086 🧐 관찰 및 접근 # 그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다. 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다. 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다. 이때 시간 복잡도는 $O(K(N+M))$이다. 이는 너무 느리다! 문제 상황을 조금 더 관찰해보자. $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다. $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다! **매개변수 탐색(파라메트릭 서치)**가 가능하다. 💻 풀이 # 코드 (C++): int N, M, K; vector<pair<int, int>> links[100010]; // (nxt, idx) vector<int> prohibit_list; int color[100010]; // 0: unvisited, 1: group A, 2: group B bool prohibited[200010]; bool isBipartite(int cnt){ rep(i, 1, M+1) prohibited[i] = false; rep(i, 0, cnt) prohibited[prohibit_list[i]] = true; rep(i, 1, N+1) color[i] = 0; rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto [nxt, idx]: links[cur]){ if(prohibited[idx]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ return false; } } } } return true; } void solve(){ cin >> N >> M >> K; rep(i, 1, M+1){ int u, v; cin >> u >> v; links[u].push_back({v, i}); links[v].push_back({u, i}); } rep(i, 0, K){ int p; cin >> p; prohibit_list.push_back(p); } // 모두 금지했을때 이분 그래프인가? if(!isBipartite(K)){ cout << -1; return; } // 파라메트릭 서치 int ok = K, ng = -1; while(ok - ng > 1){ int mid = (ok + ng) >> 1; if(isBipartite(mid)) ok = mid; else ng = mid; } cout << ok << "\n"; int groupA_sz = 0, groupB_sz = 0; isBipartite(ok); rep(i, 1, N+1) color[i] == 1 ? groupA_sz++ : groupB_sz++; cout << min(groupA_sz, groupB_sz) << ' ' << max(groupA_sz, groupB_sz) << "\n"; } 🔒 구현 코드 잠금