https://www.acmicpc.net/problem/27977

 

27977번: 킥보드로 등교하기

첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개

www.acmicpc.net

지인분이 출제한 대회문제가 백준에 등록되었습니다.

문제출제라니.. 무슨 문제를 만들어야하고, 테케는 어떻게 만드는지 모르는 입장에서 그저 신기하네요 ㅋㅋㅋ

다행히 제가 풀수있는 문제를 만들어 주셨습니다 ㅎㅎ

 

이 문제는 0에서 출발하여 L까지 정해진 배터리 용량으로 목적지까지 가야합니다.

충전소는 N개, A[i] 지점마다 있으며, 최대 K번 충전이 가능합니다.

이 때 최초 구매할 수 있는 배터리 용량의 최소를 구하는 문제입니다.

 

최종으로 구해야 하는건 배터리 용량의 최소이므로 이를 파라매트릭 서치로 구해야 합니다.

목적지까지는 갈 수 있어야하므로 최소 용량 l은 maxDis가 되겠고, 최대 용량 r은 출발지점에서 목적지까지의 거리 L이 되겠습니다.

maxDis는 출발지점과 첫 번째 충전소, 각 인접한 충전소들, 마지막 충전소와 도착지점 사이의 거리의 최대입니다.

그리고 계산의 편의를 위해 배열에 도착지점인 L을 추가합니다.

이 문제는 충전소의 위치가 정렬된 상태로 주어지므로 정렬로직이 필요 없습니다.

 

그러면 배터리 용량이 m이라고 했을 때, 충전소를 K번 이하 방문하면서 목적지점인 L 까지 갈 수 있는지 확인합니다.

L에 도착했을 때 충전소를 K번 이하로 방문할 수 있다면 ret을 갱신하고 범위를 작게 맞춰서 최적 해를 구합니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX_N 100001
using namespace std;
 
int list[MAX_N];
int L, N, K, maxDis;
 
void func() {
    int l = maxDis;
    int r = L;
 
    int ret = 0;
    while (l <= r) {
        int m = (l + r) / 2;
 
        int now = m;
        int pos = 0;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] - pos > now) {
                cnt++;
                now = m;
            }
            now -= (list[i] - pos);
            pos = list[i];
        }
 
        if (cnt <= K) {
            ret = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> L >> N >> K;
 
    int pre = 0;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        maxDis = max(maxDis, list[i] - pre);
        pre = list[i];
    }
    maxDis = max(maxDis, L - pre);
    list[N++] = L;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

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

boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22

https://www.acmicpc.net/problem/18113

 

18113번: 그르다 김가놈

첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다.

www.acmicpc.net

김밥의 꼬다리를 K * 2 만큼 잘라낸 김밥을 손질된 김밥이라고 하며, K * 2보다 작은 김밥은 K만큼만 잘라낸다고 합니다.

그 손질된 김밥을 길이가 P인 조각으로 잘라내 최소 M개의 조각을 만드려고 합니다.

-> 최소 M개의 조각을 만들기 위한 최대 P를 구하는 문제로 파라매트릭 서치를 이용합니다.

 

파라매트릭 서치는 이분탐색과 큰 차이는 없으며,

이분탐색이 정확히 M인 값을 구하는 반면, 파라매트릭 서치는 M에 가장 가까운 최적의 값을 구하는 것입니다.

 

 

이 문제는 두 가지 방법을 선택하여 해결할 수 있습니다.

먼저, 모든 김밥에 대해 최적의 P를 구하는 방법입니다.

이 방법은 입력을 그대로 다 받아놓고, 파라매트릭 서치 과정에서 K * 2 or K를 빼는 식이 포함되는 방법입니다.

 

아니면, 애초에 K보다 작거나 K * 2와 같은 길이의 김밥을 먼저 제외하여 최적의 P를 구하는 방법입니다.

이 방법은 입력을 받을 때 미리 K * 2 or K를 빼는 식이 포함되는 방법입니다.

이 과정에서 꼬다리를 제거했을 때 길이가 0 이하가 되는 김밥을 제외합니다.

두 방법 모두 AC를 받는데는 문제가 없으나 두번째 방법이 더 적은 갯수로 구할 수 있으므로 시간상 이득을 볼 수 있습니다.

 

파라매트릭 과정에서 필요없는 김밥을 제외
입력 과정에서 필요없는 김밥을 제외

두 방법으로 제출했을 때 확실히 미리 제외한 방법이 시간상 효율적이었습니다.

 

파라매트릭 서치 과정에서는

l, r은 김밥조각의 길이인 P의 범위이며, 김밥을 m으로 나눈 몫을 카운팅한 값이 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
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> list;
int N, K, M, l, r;
 
void func() {
    int ans = -1;
    l = 1;
    while (l <= r) {
        int m = (l + r) >> 1;
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] <= K) continue;
 
            if (list[i] >= K * 2) cnt += ((list[i] - K * 2) / m);
            else cnt += ((list[i] - K) / m);
        }
 
        if (cnt >= M) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    int x;
    cin >> N >> K >> M;
    for (int i = 0; i < N; i++) {
        cin >> x;
 
        list.push_back(x);
        r = max(r, x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

[처음부터 필요없는 김밥을 제외한 코드]

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> list;
int N, K, M, l, r;
 
void func() {
    int ans = -1;
    l = 1;
    while (l <= r) {
        int m = (l + r) >> 1;
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            cnt += (list[i] / m);
        }
 
        if (cnt >= M) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    int x;
    cin >> N >> K >> M;
    for (int i = 0; i < N; i++) {
        cin >> x;
        if (x <= K || x == K * 2) continue;
 
        int sub = x;
        if (x < K * 2) sub -= K;
        else sub -= (K * 2);
 
        list.push_back(sub);
        r = max(r, sub);
    }
 
    N = list.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 27977 킥보드로 등교하기  (4) 2023.04.22
boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22

https://www.acmicpc.net/problem/2295

 

2295번: 세 수의 합

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최

www.acmicpc.net

집합 U에 포함된 원소들 중 세 수를 골라 더한 a + b + c = d 값도 집합 U에 포함되는 가장 큰 d를 찾는 문제입니다.

N이 최대 1000개이므로 N^3으로 구하면 시간 초과가 뜨기 때문에 다른 방법을 생각해봅니다.

 

우선 이 문제에서 세 수를 고를 때 중복이 허락됩니다.

즉, U = {2, 3, 5, 10, 15}에서 5를 세 번 골라 5 + 5 + 5 = 15가 될 수 있다는 뜻입니다.

이것을 고려하여 문제에 접근합니다.

 

먼저 위에서 기술한 a + b + c = d를 조금 변형하면 a + b = d - c가 됩니다.

그러면 N^2으로 a + b의 모든 경우를 구할 수 있습니다. 구한 값들은 따로 벡터에 저장해둡니다.

그러면 N^2으로 d - c도 구할 수 있으며, 이분 탐색으로 a + b == d - c인 d를 구한다면

시간은 N^2 * logN으로 줄어들 수 있습니다.

 

물론 upper_bound - lower_bound를 이용하여 갯수를 구하여 풀 수도 있지만 최적의 해를 구하는 문제가 아니고,

정확한 값이 있는지 찾기만 하면 되기 때문에 일반적인 이분 탐색으로도 풀 수 있습니다.

 

d - c를 기준으로 a + b를 탐색 해야하므로 v를 정렬해줍니다.

그 다음 이분 탐색으로 v[m] == dc인 경우를 찾아주고, max인 d를 출력해줍니다.

 

그리고 문제에서 고려한 다른 부분입니다.

1. 이 문제에서 입력은 자연수만 올 수 있으므로 d - c <= 0인 경우는 미리 배제할 수 있습니다.

2. d의 최댓값을 출력해야 하므로 순회하면서 max를 사용해야 하지만 미리 list를 내림차순으로 정렬했으므로 찾는 즉시 list[i]를 출력해주시면 됩니다.

 

물론 이 두 가지를 모두 하지 않아도 AC를 받을 수 있습니다.

첫 번째 코드는 가지치기를 했고, a + b = d - c를 찾는 즉시 출력한 코드입니다. 역시 시간이 가장 빨랐습니다.

두 번째 코드는 가지치기를 하지 않았고, a + b = d - c를 찾는 즉시 출력하였습니다.

세 번째 코드는 가지치기를 했고, a + b = d - c인 모든 경우의 max를 구했습니다.

네 번째 코드는 가지치기를 하지 않았고, a + b = d - c인 모든 경우의 max를 구했습니다.

 

4개의 결과 모두 이 문제에서는 시간 차이가 별로 없을 수 있지만 범위가 커진다면 차이도 분명 커질 것입니다.

만약 테스트나 대회문제를 푼다면 두 가지를 모두 하는 것이 좋습니다.

상황에 맞는 알고리즘을 선택하고, 가지치기의 중요성을 깨닫게 하는 문제였습니다.

 

 

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
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1001
using namespace std;
 
vector<int> v;
int list[MAX];
int N;
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            v.push_back(list[i] + list[j]);
        }
    }
    sort(v.begin(), v.end());
 
    int vsize = v.size();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int dc = list[i] - list[j];
            if (dc <= 0) continue;
 
            int l = 0;
            int r = vsize - 1;
            while (l <= r) {
                int m = (l + r) / 2;
 
                if (v[m] == dc) {
                    cout << list[i] << '\n';
                    return;
                }
                else if (v[m] > dc) {
                    r = m - 1;
                }
                else {
                    l = m + 1;
                }
            }
        }
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    sort(list, list + N, [](int a, int b) {
        return a > b;
    });
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 27977 킥보드로 등교하기  (4) 2023.04.22
boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22

www.acmicpc.net/problem/2110

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

M개의 공유기를 놓을 수 있는 최대한의 간격을 구하는 문제입니다.

최대한의 간격은 최적화된 정답을 구하는 것이므로 파라매트릭 서치로 해결합니다.

 

우선 이분탐색을 쓰기 위해 입력받은 위치정보를 정렬합니다.

탐색 범위는 간격이며, (1 ~ list[N] - list[1])의 범위에서 탐색합니다.

 

간격 m에서 공유기를 M개 이상 놓을 수 있는지 확인합니다.

놓을 수 있으면 true, 아니면 false를 리턴합니다.

 

solve함수의 리턴 값이 true면 ans에 현재 간격을 저장하고 (m + 1 ~ r) 범위를 탐색합니다.

solve함수의 리턴 값이 false면 (s ~ m - 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
#include <iostream>
#include <algorithm>
using namespace std;
 
int list[200001];
int N, M;
 
bool solve(int length) {
    int pre = list[1];
    int cnt = 1;
    for (int i = 2; i <= N; i++) {
        if (list[i] - pre >= length) {
            cnt++;
            pre = list[i];
        }
    }
 
    if (cnt >= M) return true;
    else return false;
}
 
int binarySearch(int l, int r) {
    int ans = 0;
 
    while (l <= r) {
        int m = (l + r) / 2;
        if (solve(m)) {
            ans = m;
            l = m + 1;
        }
        else r = m - 1;
    }
 
    return ans;
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    sort(list + 1, list + 1 + N);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << binarySearch(1, list[N] - list[1]) << '\n';
 
    return 0;
}
 cs

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

boj 18113 그르다 김가놈  (0) 2022.10.09
boj 2295 세 수의 합  (0) 2022.06.28
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22

https://www.acmicpc.net/problem/7453

 

7453번: 합이 0인 네 정수

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

www.acmicpc.net

upperbound와 lowerbound를 연습하기 위해 풀었습니다..

 

emoney96.tistory.com/36

 

이 문제도 위의 문제와 같이 두 그룹으로 나눠서 이분탐색을 통해 값의 조합을 구하는 문제입니다.

 

먼저 list가 4개씩 주어지는데 크기가 4000이므로 2차원 배열을 이용하여 두 그룹으로 나눠줍니다.

 

그 다음 이분탐색으로 합이 0이되는 조합의 갯수를 upperbound-lowerbound로 찾아주면 되겠습니다.

 

 

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
78
79
80
81
82
83
84
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][], N;
    static long sumlist[][], ans;
 
    static int upperbound(int l, int r, long x) {
        while (l < r) {
            int m = (l + r) / 2;
            if (sumlist[1][m] <= x)
                l = m + 1;
            else
                r = m;
        }
 
        return l;
    }
 
    static int lowerbound(int l, int r, long x) {
        while (l < r) {
            int m = (l + r) / 2;
            if (sumlist[1][m] < x)
                l = m + 1;
            else
                r = m;
        }
 
        return r;
    }
 
    static void binarysearch(int l, int r, long x) {
        if (l > r)
            return;
 
        int m = (l + r) / 2;
        if (sumlist[1][m] + x == 0) {
            ans += (upperbound(0, N * N, sumlist[1][m]) - lowerbound(0, N * N, sumlist[1][m]));
            return;
        } else if (sumlist[1][m] + x < 0)
            binarysearch(m + 1, r, x);
        else
            binarysearch(l, m - 1, x);
    }
 
    static void func() {
        Arrays.sort(sumlist[1]);
        for (int i = 0; i < N * N; i++) {
            binarysearch(0, N * N - 1, sumlist[0][i]);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[4][N];
        sumlist = new long[2][N * N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[0][i] = Integer.parseInt(st.nextToken());
            list[1][i] = Integer.parseInt(st.nextToken());
            list[2][i] = Integer.parseInt(st.nextToken());
            list[3][i] = Integer.parseInt(st.nextToken());
        }
 
        for (int i = 0, k = 0; i < N; i++) {
            for (int j = 0; j < N; j++, k++) {
                sumlist[0][k] = list[0][i] + list[1][j];
                sumlist[1][k] = list[2][i] + list[3][j];
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        System.out.println(ans);
    }
}
 cs

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

boj 2295 세 수의 합  (0) 2022.06.28
boj 2110 공유기 설치  (0) 2021.04.13
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22

https://www.acmicpc.net/problem/2143

 

2143번: 두 배열의 합

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다

www.acmicpc.net

A배열의 연속 합 + B배열의 연속 합의 조합을 찾는 문제입니다.

 

A와 B 배열 각각의 연속합을 모두 저장한 후 이분탐색으로 사용하였습니다.

 

Alist의 값과 더할 Blist의 값을 이분탐색으로 찾아야하는데 중복된 값이 들어있을 수 있으므로 upper bound와 lower bound를 이용해야합니다.

 

C++에는 upper_bound와 lower_bound가 지원되어 편리하지만 JAVA에는 없어서..

직접구현 해본적도 없는 얘내들 구현한다고 고생좀 했습니다 ㅠㅠ

 

 

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int A[], B[], Adp[], Bdp[];
    static ArrayList<Long> Alist, Blist;
    static int N, M;
    static long T, ans;
 
    static void init() {
        Alist = new ArrayList<>();
        Blist = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = i; j <= N; j++) {
                Alist.add((long) (Adp[j] - Adp[i - 1]));
            }
        }
 
        for (int i = 1; i <= M; i++) {
            for (int j = i; j <= M; j++) {
                Blist.add((long) (Bdp[j] - Bdp[i - 1]));
            }
        }
 
        Collections.sort(Alist);
        Collections.sort(Blist);
    }
 
    static long upperbound(int l, int r, long x) {
        r++;
        while (l < r) {
            int m = (l + r) / 2;
            if (Blist.get(m) <= x)
                l = m + 1;
            else
                r = m;
        }
        return l;
    }
 
    static long lowerbound(int l, int r, long x) {
        r++;
        while (l < r) {
            int m = (l + r) / 2;
            if (Blist.get(m) < x)
                l = m + 1;
            else
                r = m;
        }
        return r;
    }
 
    static void binarysearch(int l, int r, long x) {
        if (l > r)
            return;
 
        int m = (l + r) / 2;
        long sum = x + Blist.get(m);
        if (sum == T) {
            ans += (upperbound(0, Blist.size() - 1, Blist.get(m)) - lowerbound(0, Blist.size() - 1, Blist.get(m)));
            return;
        } else if (sum > T)
            binarysearch(l, m - 1, x);
        else
            binarysearch(m + 1, r, x);
    }
 
    static void func() {
        for (int i = 0; i < Alist.size(); i++) {
            binarysearch(0, Blist.size() - 1, Alist.get(i));
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = new int[N + 1];
        Adp = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            Adp[i] = Adp[i - 1] + A[i];
        }
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        B = new int[M + 1];
        Bdp = new int[M + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
            Bdp[i] = Bdp[i - 1] + B[i];
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        func();
        System.out.println(ans);
    }
}
cs

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

boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22
boj 17124 두 개의 배열  (0) 2021.01.22

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

 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

잘려진 나무의 길이를 적어도 M으로 하기위한 높이의 최댓값을 구하는 문제입니다.

최적의 값을 구하는 문제이기때문에 이분탐색 중에서 파라매트릭 서치를 이용하여 해결할 수 있습니다.

 

높이를 1~list중 최대로 설정하여 파라매트릭 서치를 돌리고

잘려진 나무의 높이의 합이 M보다 작으면 l ~ m-1

잘려진 나무의 높이의 합이 M보다 크거나 같으면 m+1~r

로 높이를 재설정하여 구하면 됩니다.

 

최적의 값을 구해야하기 때문에 합이 M이라고 해서 바로 리턴해버리는 실수가 없어야합니다.

(합이 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
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[];
    static int N, M, maxheight;
    static long ans = 0;
 
    static void binarysearch(long l, long r) {
        if (l > r)
            return;
 
        long m = (l + r) / 2;
        long sum = 0;
        for (int i = 1; i <= N; i++) {
            if (list[i] <= m)
                continue;
            sum += (list[i] - m);
        }
 
        if (sum >= M) {
            ans = Math.max(ans, m);
            binarysearch(m + 1, r);
        } else {
            binarysearch(l, m - 1);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            maxheight = Math.max(maxheight, list[i]);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        binarysearch(1, maxheight);
        System.out.println(ans);
    }
}
cs

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

boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22
boj 17124 두 개의 배열  (0) 2021.01.22

https://www.acmicpc.net/problem/1920

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

가장 기본적인 이분탐색 알고리즘으로 해결 가능한 문제입니다.

 

주의할 점은 처음에 주어지는 배열의 크기인 N과

수가 배열안에 존재하는지 확인하는 배열의 크기인 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[];
    static int ques[];
    static int N, M;
 
    static int binarysearch(int l, int r, int x) {
        if (l > r)
            return 0;
 
        int m = (l + r) / 2;
        if (list[m] == x)
            return 1;
        else {
            if (list[m] > x)
                return binarysearch(l, m - 1, x);
            else
                return binarysearch(m + 1, r, x);
        }
    }
 
    static void func() {
        for (int i = 1; i <= M; i++) {
            System.out.println(binarysearch(1, N, ques[i]));
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        ques = new int[M + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            ques[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

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

boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22
boj 17124 두 개의 배열  (0) 2021.01.22

 

https://www.acmicpc.net/problem/17124

 

17124번: 두 개의 배열

정수 배열 A 와 B가 있다. A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A, B를 이용해서 길이가 n인 새로운 배열 C를 만들어보자. C[i] 는 배열 B에 있

www.acmicpc.net

C[i]는 배열 B에 있는 값 중에 A[i]에 가장 가까운 값이고 가장 가까운 값이 2개면 더 작은값입니다.

배열의 크기가 100만이므로 선형으로 찾기에는 무조건 시간초과이므로 이분탐색을 사용합니다.

(이분탐색을 위해 B 배열을 정렬해줍니다.)

 

A[i]가 주어지면

B 배열에서 A[i]보다 작은 값중에 가장 큰 값 = l

B 배열에서 A[i]보다 큰 값중에 가장 작은 값 = r

이러면 l과 r 둘중에 하나는 정답입니다.

 

abs(A[i] - l) vs abs(A[i] - r)를 비교하여 차이가 적은 값 (차이가 같으면 둘 중에 작은 값) 을 ans에 더해줍니다.

배열에 10^9까지 올 수 있으므로 long long 타입으로 계산하였습니다.

 

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
78
79
80
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;
typedef long long ll;
 
int A[1000001], B[1000001];
int N, M;
ll ans;
 
int largesearch(int l, int r, int x) {
    int m = (l + r) / 2;
 
    if (B[m] == x) return B[m];
    else if (B[m] > x) {
        if (l == m) return B[m];
        else return min(B[m], largesearch(l, m - 1, x));
    }
    else {
        if (m == r) return INF;
        else return largesearch(m + 1, r, x);
    }
}
 
int smallsearch(int l, int r, int x) {
    int m = (l + r) / 2;
 
    if (B[m] == x) return B[m];
    else if (B[m] < x) {
        if (m == r) return B[m];
        else return max(B[m], smallsearch(m + 1, r, x));
    }
    else {
        if (l == m) return -1;
        else return smallsearch(l, m - 1, x);
    }
}
 
void func() {
    int l = 0, r = 0;
    for (int i = 1; i <= N; i++) {
        l = smallsearch(1, M, A[i]);
        r = largesearch(1, M, A[i]);
        if (l == -1) l = B[1];
        if (r == -1) r = B[M];
 
        if (abs(A[i] - l) <= abs(r - A[i])) {
            ans += l;
        }
        else ans += r;
    }
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
 
    for (int i = 1; i <= M; i++) {
        cin >> B[i];
    }
    sort(B + 1, B + 1 + M);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
        ans = 0;
    }
 
    return 0;
}
 cs

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

boj 2110 공유기 설치  (0) 2021.04.13
boj 7453 합이 0인 네 정수  (0) 2021.01.22
boj 2143 두 배열의 합  (0) 2021.01.22
boj 2805 나무 자르기  (0) 2021.01.22
boj 1920 수 찾기  (0) 2021.01.22

+ Recent posts

티스토리툴바