3151번: 합이 0
Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다.
www.acmicpc.net
이 문제는 이전 포스팅에서 다루었던 백준 2473 - 세 용액 문제의 살짝 업그레이드 버전이라고 생각한다.
세 용액 문제에서는 0에 가까운 값을 찾기만 하면 되기 때문에 가장 가까운 인덱스들만 확인하면 되었다. 하지만 이번에는 0이 되는 모든 경우의 수를 합산해야 한다. 물론 그냥 전부 확인하려면 시간 초과가 나게 된다. 이번에도 이분탐색과 정렬의 힘을 활용하자!
문제의 예제에 대한 설명은 문제에 잘 되어있으므로, 한 가지 다른 예시를 만들어보자. 위의 그림에서처럼 0이 여러 번있는 경우가 다루기 까다로울 수 있는 케이스 중 하나일 것이다. 0이 여러 개가 있기 때문에, 위의 그림에서처럼 조합을 통해 선택하면 총 10가지가 있다는 사실을 알게 된다. 하지만 루프를 돌며 일일이 셀 순 없다. 어떻게 하면 빨리 확인할 수 있을까? 항상 그렇듯이, 카운트를 일일이 하지 않고, 한 번의 연산으로 카운트를 끝내야 한다. 수열이 정렬되어있기에 이것이 가능하다.
위와 같이 앞에 2개의 수가 선택되어 있다면, 두 수의 합을 알게 되고, 그를 통해 목표값을 알게 된다. 해당 목표값이 어디에 있는지를 lower_bound와 upper_bound를 통해 파악할 수 있게 되고, 그 두 결과의 차가 바로 개수가 되는 것이다. lower_bound는 목표값을 포함한 인덱스를 리턴하고 upper_bound는 목표보다 큰 값의 인덱스를 리턴하므로, 차를 구해서 개수를 한 번에 알 수 있다. 하지만 이분탐색을 행하므로 로그 시간이 매 루프 회차마다 있게 되고, 총 시간복잡도는 O(n^2 log n)이 된다.
lower_bound는 C++에 있는 내장함수인데 이 함수는 이분탐색을 통해 원하는 값의 위치를 찾는다. 그에 관련한 내용은 아래의 링크를 통해 간략하게 확인 가능하다.
t-anb.tistory.com/18?category=823764
이분탐색
기본적이면서도 너무나도 강력한 이분탐색에 대한 정리를 하고자 한다. 이분탐색이란 말 그대로 일정한 구간, 범위 등을 2개로 나누어 탐색 범위를 좁혀나가는 것을 말한다. 시간복잡도를 따질
t-anb.tistory.com
투 포인터를 활용한 풀이도 있다. 이후에 생각나면 추가하도록 하겠다.
<주요 내용>
이분탐색, 정렬, 투 포인터
<코드>
문제 풀이시에 정답의 범위(int)에 주의한다.
#include <iostream>
#include <algorithm>
typedef long long ll;
#define endl '\n'
using namespace std;
const int sz=1e4;
int arr[sz],n,temp,idx,idx2;
ll cnt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=0;i<n;++i)cin>>arr[i];
sort(arr,arr+n);
for(int i=0;i<n-2;++i){
for(int j=i+1;j<n-1;++j){
temp=(-1)*(arr[i]+arr[j]);
idx=lower_bound(arr+j+1,arr+n,temp)-arr;
idx2=upper_bound(arr+j+1,arr+n,temp)-arr;
cnt+=idx2-idx;
}
}
cout<<cnt<<endl;
return 0;
}
