합이 0인 네 정수




크기가 N으로 같은 정수형 배열 네 개가 주어질 때,


각 배열의 원소를 하나 씩 골라서 더했을 때 0을 만들 수 있는 경우가 얼마나 되는지 계산해야 한다.



모든 경우를 시도해보고 0인 가짓수를 세 보면 가능하지만, 


N이 최대 사천이므로 N^4 으로 시간초과가 날 것이므로, 불가능함이 자명한 경우를 추리는 최적화가 필요하다.



예를 들어 세 정수의 합이 300 인데, 나머지 한 배열의 원소 중에 임의의 수를 더해봤더니 0보다 작다면,


그 수보다 작은 원소들은 시도해볼 필요가 없다.



따라서 이분 탐색을 통해 시간복잡도를 줄이기로 한다.


세 배열을 모두 더해보고 남은 한 배열에서 찾는다면 4000^3의 계산과정이 필요하다.


하지만 두 배열 씩 더해서 새로운 배열 두 개를 만들고, 한쪽 배열의 모든 원소를 다른 배열에서 이분탐색한다면,


새로운 배열 생성에 2 * 4000 ^ 2 만큼 걸리고, 남은 이분 탐색에선 4000 ^ 2 * log (4000 ^ 2) 만큼 걸린다.



주의할 점은, 중복의 경우를 세야 한다는 것이다.


예를 들어 한 쪽 배열에서 -40이란 원소에 의해 다른 배열에서 40을 찾는 경우에, 40은 중복해서 존재할 수 있다.


 

찾는 값은 lower_bound와 upper_bound의 차이 만큼 중복으로 존재한다.


만약 두 함수의 결과에 차이가 없다면, 다음 원소의 탐색시엔 upper_bound부터 탐색해도 무방하다.


코드로 옮기자면 다음과 같다.


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, nn;
int ab[16000000], cd[16000000];
int a[4000], b[4000], c[4000], d[4000];
 
 
int main() {
    scanf("%d", &n);
    nn = n*n;
 
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ab[n*i + j] = -(a[i] + b[j]);
            cd[n*i + j] = c[i] + d[j];
        }
    }
 
    sort(cd, cd + nn);
 
    int left = 0, right = nn;
    long long ans = 0;
 
    for (int i = 0; i < nn; ++i) {
 
        while (left < right) {
            int mid = (left + right) / 2;
 
            if (ab[i] > cd[mid])
                left = mid + 1;
            else
                right = mid;
        }
 
        int lo = right;
        //int lo2 = lower_bound(cd, cd + nn, ab[i]) - cd;
 
        left = 0, right = nn;
        
        while (left < right) {
            int mid = (left + right) / 2;
 
            if (ab[i] >= cd[mid])
                left = mid + 1;
            else
                right = mid;
        }
 
        int hi = right;
        //int hi2 = upper_bound(cd, cd + nn, ab[i]) - cd;
 
        ans += (long long)(hi - lo);
 
        left = 0, right = nn;
    }
 
    printf("%lld", ans);
 
    return 0;
}
cs


'알고리즘 > 이진 탐색' 카테고리의 다른 글

백준) 1654 랜선 자르기  (2) 2018.01.09
백준) 2805 나무 자르기  (2) 2018.01.09

랜선 자르기


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



나무 자르기(http://js1jj2sk3.tistory.com/64?category=749321)와 비슷한 문제다.


K개의 랜선을 적절하게 같은 길이로 잘라 N개의 랜선을 만들어야 하는데,


N개를 만들지 못하는 경우는 없다고 주어졌다.



길이는 모두 정수 값이므로, 나무 자르는 문제와 같이 가능한 모든 길이를 시도해 보면 된다.


마찬가지로 이분 탐색으로 범위를 줄여나갈 수 있고, 현재 시도 중인 길이에 대해 두 가지 케이스가 발생한다.



1. 잘라봐도 N개를 만들지 못할 때


더 긴 길이로 잘라봐야 만들지 못할것이 자명하므로 왼쪽 부분으로 좁혀서 탐색한다.


2. 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
#include <stdio.h>
using namespace std;
 
int k, n;
int lan[10000];
 
bool chk(int mid) {
    int cnt = 0;
 
    for (int i = 0; i < k; ++i)
        cnt += lan[i] / mid;
 
    return cnt >= n;
}
 
int main() {
    scanf("%d %d", &k, &n);
 
    int max = 0;
    for (int i = 0; i < k; ++i) {
        scanf("%d", &lan[i]);
        if (max < lan[i])
            max = lan[i];
    }
    
    long long left = 1, right = max;
    int ans = 0;
 
    while (left <= right) {
        long long mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (mid > ans)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


left를 초기화 할 때 1이 아닌 0으로 한다면 mid가 0이 되버려 런타임 오류가 발생할 수도 있다.

'알고리즘 > 이진 탐색' 카테고리의 다른 글

백준) 7453 합이 0인 네 정수  (0) 2018.01.10
백준) 2805 나무 자르기  (2) 2018.01.09

나무 자르기

 

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

 

 

시도해 볼 수 있는 높이는 모두 정수다.

 

따라서 모든 가능한 정수에 대해서 시도해보면, M보다 크거나 같은 결과가 나오는 높이들을 파악할 수 있고,  그 중 가장 큰 정수를 찾으면 된다.

 

 

하지만 모든 정수를 시도해 볼 필요는 없다.

 

만약 300의 높이로 시도해 보았을 때, M보다 작은 결과가 나온다면, 300보다 높은 높이로 시도했을 때도 당연히 실패할 것이기 때문이다.

 

 

따라서 가능한 결과들은 한 구간으로만 나올 것이다.

 

우리가 할 것은 그 구간을 빠르게 찾는 것이다.

 

 

이진 탐색으로 빠르게 구간을 찾을 수 있다. 

 

1/2 씩 구간을 줄여나가는 방벙으로, n개의 수를 로그시간에 탐색할 수 있다.

 

 

정수의 범위는 1부터 가장 높은 나무의 높이 까지다.

 

주어진 나무 높이의 합이 M보다 크다는 조건 때문에 1을 계산해볼 필요가 없다.

 

가장 큰 높이로 자르면 당연히 합이 0일 것이므로 계산해볼 필요가 없다.

 

 

이제부터 중간값으로 구간을 줄여보자.

 

중간 높이로 자르고 나면 두 가지 경우가 생긴다.

 

 

1. 잘린 나무의 합이 M보다 작을 경우

 

현재 높이보다 낮은 높이로 시도해 보아야 한다. 왼쪽 구간으로 변경

 

2. 잘린 나무의 합이 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
#include <stdio.h>
using namespace std;
 
int n, m;
long long tree[1000000];
 
bool chk(int mid) {
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        if (mid < tree[i])
            sum += tree[i] - mid;
    }
 
    return sum >= m;
}
 
int main() {
    scanf("%d %d", &n, &m);
 
    int max = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &tree[i]);
        if (tree[i] > max)
            max = tree[i];
    }
 
 
    int left = 0, right = max;
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}
 cs

 

나무의 높이들을 저장하는 배열을 정렬해 둔다면, 정수 값을 1씩 옮기지 않고 구간을 옮길 수 있으므로

 

최적화가 가능할 것 같다.

 

'알고리즘 > 이진 탐색' 카테고리의 다른 글

백준) 7453 합이 0인 네 정수  (0) 2018.01.10
백준) 1654 랜선 자르기  (2) 2018.01.09

+ Recent posts

티스토리툴바