BOJ : https://www.acmicpc.net/problem/11662

github : https://github.com/junho0956/Algorithm/blob/master/11662/11662/%EC%86%8C%EC%8A%A4.cpp

 

삼분탐색의 기본개념을 통해 구현하였으며 설명은 코드에 주석처리 해놓았으니 참고하시면 될 것 같습니다.

삼분탐색 기본개념 : https://junho0956.tistory.com/128?category=869180

 

더보기
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
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)
 
typedef pair<double, double> pii;
 
// x -> 0 // y -> 1
// start : 시작점 end : 끝점
int minho_start[2], minho_end[2];
int kangho_start[2], kangho_end[2];
 
pii minho_move(double p) {
    return make_pair(minho_start[0] + (minho_end[0] - minho_start[0]) * (p / 100), minho_start[1] + (minho_end[1] - minho_start[1]) * (p / 100));
}
 
pii kangho_move(double p) {
    return make_pair(kangho_start[0] + (kangho_end[0] - kangho_start[0]) * (p / 100), kangho_start[1] + (kangho_end[1] - kangho_start[1]) * (p / 100));
}
 
int main() {
    scanf("%d%d%d%d", &minho_start[0], &minho_start[1], &minho_end[0], &minho_end[1]);
    scanf("%d%d%d%d", &kangho_start[0], &kangho_start[1], &kangho_end[0], &kangho_end[1]);
 
    double first_percent = 0, last_percent = 100, length = sqrt(pow(10000, 2) + pow(10000, 2));
    // 오차는 10^-6 까지 허용한다는 것은 ...
    // 10^-6 까지는 맞춰야된다는 건가? 그럼 10^-7 까지의 오차만 확인해본다면
    while (last_percent - first_percent >= 1e-7) {
        double p1, p2;
        // 삼등분 했을 때 좌표
        p1 = (2 * first_percent + last_percent) / 3, p2 = (first_percent + 2 * last_percent) / 3;
 
        // p1 과 p2 를 이용하여 p1 , p2 만큼 이동했을 때 민호와 강호의 좌표를 구함
        // m1 -> minho_move_p1, m2 -> minho_move_p2 , k1, k2 ,,
 
        pii m1 = minho_move(p1), m2 = minho_move(p2);
        pii k1 = kangho_move(p1), k2 = kangho_move(p2);
 
        // 구해야하는 것은 민호와 강호의 p1, p2 만큼 이동했을 때의 거리
        // p1 에 의한 거리
        double len_p1 = sqrt(pow(m1.first - k1.first, 2) + pow(m1.second - k1.second, 2));
        double len_p2 = sqrt(pow(m2.first - k2.first, 2) + pow(m2.second - k2.second, 2));
 
        length = min(min(len_p1, len_p2), length);
 
        // 삼분탐색 조건에 따라서
        // 만약 len_p1 의 길이가 len_p2 의 길이보다 작다면 len_p2 쪽에는 최소값이 없으므로
        if (len_p1 <= len_p2) last_percent = p2;
        else first_percent = p1;
    }
    // 오차가 10^-6 까지는 허용    => 10^-6 까지는 검사 ==> 10^-7 까지만 출력해보면 
    printf("%.7f", length);
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1780번 종이의 개수  (0) 2020.01.17
BOJ 11728번 배열 합치기  (0) 2020.01.17
BOJ 10816번 숫자 카드2  (0) 2020.01.16
BOJ 10815번 숫자 카드  (0) 2020.01.16
BOJ 2110번 공유기 설치  (0) 2020.01.16

BOJ : https://www.acmicpc.net/problem/10816

github : https://github.com/junho0956/Algorithm/blob/master/10816/10816/%EC%86%8C%EC%8A%A4.cpp

 

숫자의 존재여부를 찾았다고 해서 무작정 좌우로 -1, +1 씩 해가면서 갯수를 확인하면

카드갯수가 최대 50만개, 테스트케이스가 50만개이기때문에 무조건 시간초과에 걸린다.

 

숫자의 존재여부를 알았다면 재 탐색을 통해 그 숫자의 첫번째 위치, 마지막 위치를 찾아주어야 한다.

이 때 알면 좋은 개념이 lower_bound 와 upper_bound 이다.

lower_bound 는 찾고자하는 값 이상의 값이 처음으로 위치하는 곳을 탐색하는 것으로

예를 들어 배열이 1 3 3 5 5 6 6 6 8 9 이고 찾고자 하는 값이 6 이면 위치는 5 이다.

upper_bound 는 찾고하는 값보다 큰! 값이 처음으로 위치하는 곳을 탐색하는 것으로

예를 들어 배열이 1 3 3 5 5 6 6 6 8 9 이고 찾고자 하는 값이 6 이면 위치는 8 이다.

 

lower_bound 는 코드상 왼쪽부분을 탐색하는 곳, upper_bound 는 코드상 오른쪽부분을 탐색하는 곳 으로

나누어 해결하였다.

 

중요한 것은 upper_bound 를 하게되면 찾고하자하는 값 보다 큰 값이 존재하지 않을 수도 있다.

위의 배열에서 9에 대한 upper_bound 를 실행한다면 위치는 9를 반환하게 된다.

그렇기 때문에 upper_bound 를 실행한 후에 만약 리턴받은 위치에 대한 배열값이 찾고하 하는 값과 같다면

위치에 대한 -1 작업을 해주지 않아도 된다.

 

더보기
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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int search(int s, int e, int k) {
    int mid, cnt = 0;
    int ss = s, ee = e;
    bool check = false;
    while (ss <= ee) {
        mid = (ss + ee) / 2;
        if (v[mid] == k) {
            check = true;
            break;
        }
        else if (v[mid] > k) ee = mid - 1;
        else if (v[mid] < k) ss = mid + 1;
    }
    
    if (check) {
        int left_s = 0, left_e = mid, right_s = mid, right_e = e, left, right;
        while (left_s < left_e) {
            mid = (left_s + left_e)/2;
            if (v[mid] >= k) left_e = mid;
            else left_s = mid + 1;
        }
        left = left_e;
        while (right_s < right_e) {
            mid = (right_s + right_e) / 2;
            if (v[mid] > k) right_e = mid;
            else right_s = mid + 1;
        }
        right = right_e;
        if (v[right] != k) right--;
        return right - left + 1;
    }
    else return 0;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, n, M, m;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> n;
        v.push_back(n);
    }
    sort(v.begin(), v.end());
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> m;
        cout << search(0, N - 1, m) << ' ';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11728번 배열 합치기  (0) 2020.01.17
BOJ 11662번 민호와 강호  (0) 2020.01.16
BOJ 10815번 숫자 카드  (0) 2020.01.16
BOJ 2110번 공유기 설치  (0) 2020.01.16
BOJ 2805번 나무 자르기  (0) 2020.01.16

BOJ : https://www.acmicpc.net/problem/10815

github : https://github.com/junho0956/Algorithm/blob/master/10815/10815/%EC%86%8C%EC%8A%A4.cpp

 

숫자의 범위가 크기때문에 배열을 이용할 수는 없다.

그래서 탐색을 통해 존재여부를 찾아야하므로 가장 기본적인 binary search 를 아는지 모르는지를 묻는 문제이다.

 

더보기
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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int search(int s, int e, int k) {
    int mid;
    while (s <= e) {
        mid = (s + e) / 2;
        if (v[mid] == k) return 1;
        else if (v[mid] > k) e = mid - 1;
        else if (v[mid] < k) s = mid + 1;
    }
    if (v[s] == k || v[e] == k) return 1;
    else return 0;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, n, M, m;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> n;
        v.push_back(n);
    }
    sort(v.begin(), v.end());
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> m;
        cout << search(0, N - 1, m) << ' ';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11662번 민호와 강호  (0) 2020.01.16
BOJ 10816번 숫자 카드2  (0) 2020.01.16
BOJ 2110번 공유기 설치  (0) 2020.01.16
BOJ 2805번 나무 자르기  (0) 2020.01.16
BOJ 1654번 랜선 자르기  (0) 2020.01.16

BOJ : https://www.acmicpc.net/problem/2110

github : https://github.com/junho0956/Algorithm/blob/master/2110/2110/%EC%86%8C%EC%8A%A4.cpp

 

C개의 공유기를 N개의 집에 남김없이 설치해야하는 문제이다.

** 설치가 가능할 때 집과 집 사이의 거리중 가장 인접한(작은) 거리를 최대로 만드는 문제이다. **

코드와 함께 이분탐색의 조건을 같이 주석처리 해놓았다.

 

더보기
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, c, x;
    vector<int> v;
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
 
    int left = 1, right = v[n - 1] - v[0];
    int result_len = 0;
 
    while (left <= right) {
        int len = (left + right) / 2;
        int cnt = 1, last_house = 0;
        int min_len = INT_MAX;
        bool check = false;
        for (int i = 1; i < n; i++) {
            if (v[i] - v[last_house] >= len) {
                min_len = min(min_len, v[i] - v[last_house]);
                cnt++, last_house = i;
                if (cnt == c) {
                    check = true; break;
                }
            }
        }
        // 공유기 c개를 설치할 수 있다면 -> 현재 len 보다 더 큰 값을 
        if (check) {
            result_len = max(result_len, min_len);
            left = len + 1;
        }
        // 공유기 c개를 설치할 수 없다면
        else right = len - 1;
    }
    cout << result_len;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10816번 숫자 카드2  (0) 2020.01.16
BOJ 10815번 숫자 카드  (0) 2020.01.16
BOJ 2805번 나무 자르기  (0) 2020.01.16
BOJ 1654번 랜선 자르기  (0) 2020.01.16
BOJ 1167번 트리의 지름  (0) 2020.01.15

+ Recent posts

티스토리툴바