[3649] 로봇 프로젝트
BOJ/Parametric Search2018. 7. 24. 13:59
### Sort + Binary Search ###
[3649] 로봇 프로젝트 : http://boj.kr/3649
<소스코드>
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int x, n; vector<int> lego; void solve() { for(int i=0; i<n-1; i++) { int cur = lego[i]; if(binary_search(lego.begin()+i+1, lego.end(), x-cur)) { printf("yes %d %d\n", cur, x-cur); return ; } } puts("danger"); } int main() { while(scanf("%d", &x) == 1) { scanf("%d", &n); lego = vector<int>(n); for(int i=0; i<n; i++) { scanf("%d", &lego[i]); } x *= 10000000; sort(lego.begin(), lego.end()); solve(); } } | cs |
>> 정렬 후 i 번째 값과 x-i번째 값이 [i+1, n-1] 구간에 존재하는지 확인.
>> 시간복잡도 O(N*logN)
'BOJ > Parametric Search' 카테고리의 다른 글
| [13905] 세부 (다른방법으로 풀어보기) (0) | 2018.07.24 |
|---|---|
| [1939] 중량제한 (0) | 2018.07.24 |
[13905] 세부 (다른방법으로 풀어보기)
BOJ/Parametric Search2018. 7. 24. 02:15
### Parametric Search + BSF ###
[13905] 세부 : http://boj.kr/13905
- 다익스트라 or MST+LCA 로도 풀 수 있다고 한다. 나중에 도전해봐야겠다..!!
<소스코드>
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; struct P { int to, w; }; int n, m; int s, e; vector<P> g[100001]; bool isPossible(int mid) { queue<int> q; q.push(s); vector<bool> visited(n+1, 0); visited[s] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); for(auto &p : g[cur]) { int next = p.to; int w = p.w; if(!visited[next] && mid <= w) { if(next == e) return 1; visited[next] = 1; q.push(next); } } } return 0; } int main() { scanf("%d%d%d%d", &n, &m, &s, &e); while(m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a].push_back((P){b, c}); g[b].push_back((P){a, c}); } if(s == e) return !printf("0\n"); int S=1, E=1000000; while(S <= E) { int mid = (S+E)/2; if(isPossible(mid)) S = mid+1; else E = mid-1; } printf("%d\n", S-1); return 0; } | cs |
>> [1939] 중량제한 문제와 동일한 문제.
>> 근데 조건 한개가 다르다. 중량제한 문제는 출발지와 도착지가 서로 다르다고 명시가 되어 있는데, 위 문제는 그렇지 않다.
>> 그래서 47 라인이 추가되었다.
'BOJ > Parametric Search' 카테고리의 다른 글
| [3649] 로봇 프로젝트 (0) | 2018.07.24 |
|---|---|
| [1939] 중량제한 (0) | 2018.07.24 |
[1939] 중량제한
BOJ/Parametric Search2018. 7. 24. 01:51
### Parametric Search + BFS ###
[1939] 중량제한 : http://boj.kr/1939
<소스코드>
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 | #include <cstdio> #include <vector> #include <queue> using namespace std; struct P { int to, limit; }; int n, m; int a, b, c; vector<P> v[10001]; bool isPossible(int mid) { queue<int> q; q.push(a); vector<bool> visited(n+1, 0); visited[a] = 1; while(!q.empty()) { int cur = q.front(); q.pop(); for(auto &p : v[cur]) { int next = p.to; int c = p.limit; if(!visited[next] && mid <= c) { if(next == b) return true; q.push(next); visited[next] = 1; } } } return false; } int main() { scanf("%d%d", &n, &m); while(m--) { scanf("%d%d%d", &a, &b, &c); v[a].push_back((P){b, c}); v[b].push_back((P){a, c}); } scanf("%d%d", &a, &b); int s=1, e=1e9; while(s <= e) { int mid = (s+e)/2; if(isPossible(mid)) s = mid+1; else e = mid-1; } printf("%d\n", s-1); return 0; } | cs |
>> 중량을 mid 로 설정했을 때, 이게 답이 될 수 있으면 탐색범위를 [mid+1, e] 로 좁혀간다.
>> 답이될 수 없다면 [s, mid-1] 로 좁힌다.
'BOJ > Parametric Search' 카테고리의 다른 글
| [3649] 로봇 프로젝트 (0) | 2018.07.24 |
|---|---|
| [13905] 세부 (다른방법으로 풀어보기) (0) | 2018.07.24 |
