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

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

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

 

설명은 코드에 있습니다.

** 가장 중요한 문제의 핵심은 적어도 M 미터를 가져갈 수 있는 절단기의 높이를 최대로 만들어 주는 것입니다.

** 그래야 최소한의 나무 손실을 막으면서 원하는 만큼 가져갈 수 있습니다.

 

더보기
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
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    long long M, len, cnt, height = 0;
    vector<long long> v;
    long long left = 0, right = INT_MAX;
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> len;
        v.push_back(len);
    }
 
    while (left <= right) {
        long long mid = (left + right) / 2;
        cnt = 0;
        for (int i = 0; i < N; i++) if (v[i] >= mid) cnt += v[i] - mid;
 
        // cnt 가 M 보다 작다는 것은 절단기의 높이가 크다는 것을 의미 => 절단기의 높이를 낮춰야함
        if (cnt < M) right = mid - 1;
        // cnt 가 M 보다 크다는 것은 절단기의 높이가 작다는 것을 의미 => 절단기의 높이를 높여야함d
        else if (cnt > M) {
            left = mid + 1;
            // 적어도 M 미터를 넘게 가져갈 수 있긴 하니 현재 절단기 높이가 height 보다 크다면 갱신
            height = height < mid ? mid : height;
        }
        // 현재 cnt 가 M 미터를 정확히 가져갈 수 있다면 최적의 해
        else {
            height = mid;
            break;
        }
    }
 
    cout << height;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 10815번 숫자 카드  (0) 2020.01.16
BOJ 2110번 공유기 설치  (0) 2020.01.16
BOJ 1654번 랜선 자르기  (0) 2020.01.16
BOJ 1167번 트리의 지름  (0) 2020.01.15
BOJ 1967번 트리의 지름  (0) 2020.01.15

+ Recent posts

티스토리툴바