9502번: Bones’s Battery
boj.ma
모든 학교 간 이동을 가능하게 하는 최소 배터리 용량을 찾고싶은 문제입니다.
충전은 최대 K번 할 수 있고 시작시 용량이 0이기 때문에 시작할때 반드시 한 번 충전을 해야합니다.
용량을 최소한으로 소모하여 이동하는게 이득이기 때문에 어떤 두 정점간 최단경로로 이동하는것이 최적입니다.
문제에서 원하는 값은 "최대 K번 충전하여 모든 학교간 이동을 가능하게 하는 충전량의 최소값" 입니다.
완탐을 떠올려 보면
1회 충전 시 충전량이 1일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?
1회 충전 시 충전량이 2일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?
1회 충전 시 충전량이 3일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?
1회 충전 시 충전량이 4일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?
...
1회 충전 시 충전량이 X일 때 최대 K번 충전해서 모든 학교간 이동 가능하냐?
처럼 결정 문제로 바꿀 수 있고, 위 결정문제에 대한 정답은 단조성을 보이기 때문에 즉, 특정 용량 이후로는 항상 가능하다는 대답이 나오기 때문에 이분탐색으로 최적화가 가능합니다.
모든 정점쌍 간 최단경로를 구해야하고, N이 작기 때문에 플로이드 워셜로 최단경로를 구할 수 있습니다.
시간복잡도는 이분탐색으로 가능한 구간에 매 탐색마다 플로이드를 돌리기 때문에
$O(N^3 log_210^{11})$ 이 됩니다.
코드 (C++)
#include <bits/stdc++.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define NM 15*15+10
#define MAX 150010
#define BIAS 1048576
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using ll = long long;
using ull = unsigned long long;
int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };
int main() {
fastio;
int t;
cin >> t;
while (t--) {
int n, K, m;
cin >> n >> K >> m;
vector<vector<ll>> dist(n, vector<ll>(n, LINF));
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (int i = 0; i < m; i++) {
ll a, b, c;
cin >> a >> b >> c;
dist[a][b] = min(dist[a][b], c);
dist[b][a] = min(dist[b][a], c);
}
for (int k = 0; k < n;k++) {
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
auto ok = [&](ll x)->bool {
vector<vector<ll>> tmp(n, vector<ll>(n, INF));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n;j++) {
if (i == j) tmp[i][j] = 0;
else if (dist[i][j] <= x) tmp[i][j] = 1;
}
}
for (int k = 0; k < n;k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
tmp[i][j] = min(tmp[i][j], tmp[i][k] + tmp[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (tmp[i][j] > K) return false;
}
}
return true;
};
ll l = 0, r = LINF;
ll ans = r;
while (l <= r) {
ll mid = l + r >> 1;
if (ok(mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}
return 0;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
| 백준 33543 둘이 한 팀 (0) | 2025.03.03 |
|---|---|
| 백준 2001 보석 줍기 (2) | 2024.08.31 |
| 백준 17943 도미노 예측 (0) | 2024.07.18 |
| 백준 7346 유전자 함수 (0) | 2024.05.16 |
| 백준 23889 돌 굴러가유 (0) | 2024.05.16 |
