문제 URL : https://www.acmicpc.net/problem/2585
2585번: 경비행기
경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간
www.acmicpc.net
문제 접근법 : 최소 연료를 가지고 도착지점에 도착하는지 확인하면 되는문제입니다.
최소연료 1~최소연료가 되는구간까지 bfs든 dfs든 돌려야하는데 이렇게한다면 시간초과가 100프로니
이분탐색을 이용해야합니다. 결국엔 이분탐색 + bfs 혹은 dfs문제로 접근하면 됩니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
//By콩순이냉장고
#include <iostream>
#include <algorithm>
#include <vector>
#include<queue>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, k;
vector<pair<ll, ll>> v;
struct point {
ll x, y, cnt;
};
ll needfuel(ll x1, ll y1, ll x2, ll y2) {
ll dis = ceil(sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2)));
return dis % 10 == 0 ? dis / 10 : dis / 10 + 1;
}
void input() {
cin >> n >> k;
v.resize(n + 2);
for (int i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
}
v[n + 1].first = v[n + 1].second = 1e4;
}
bool bfs(int fuel) {
char visit[1002] = { 0 };
queue<point> q;
q.push({ 0,0,0 });
visit[0] = 1;
while (!q.empty()) {
int y = q.front().y;
int x = q.front().x;
int cnt = q.front().cnt;
q.pop();
if (needfuel(x, y, v.back().first, v.back().second) <= fuel)
return true;
if (cnt > k)
continue;
for (int i = 1; i <= n; i++) {
if (visit[i] == 0 && needfuel(x, y, v[i].first, v[i].second) <= fuel)
{
visit[i] = true;
q.push({ v[i].first,v[i].second,cnt + 1 });
}
}
}
return false;
}
void solve() {
int first = 0;
int last = 1e8;
int res = 0;
while (first <= last) {
int mid = (first + last) / 2;
if (bfs(mid)) {
last = mid - 1;
res = mid;
}
else
first = mid + 1;
}
cout << res << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 좋습니다. 댓글을 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 16434 드래곤 앤 던전 (0) | 2021.05.20 |
|---|---|
| 백준 1981 배열에서 이동 (0) | 2021.05.20 |
| 백준 8983 사냥꾼 (1) | 2021.05.14 |
| 백준 20437 문자열 게임2 (0) | 2021.05.05 |
| 백준 3687 성냥개비 (0) | 2021.04.23 |
