문제 이해 단계
https://www.acmicpc.net/problem/3151
3151번: 합이 0
Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다.
www.acmicpc.net
N개의 입력이 일렬로 들어온다. 입력은 정수로 들어오는데,
숫자가 -10,000 ~ 10,000 사이로 들어온다.
숫자 3개를 골라서 합이 0이 되는 경우가 몇 가지가 나오는지 찾는 문제.
숫자가 같아도 위치가 다르면 다른 경우의 수로 취급한다.
문제 접근 단계
제한사항부터 살펴보면 N개의 입력은 최대 10,000개까지 들어올 수 있다.
숫자가 3개를 골라야 하기 때문에
10000 C3 = (10000 * 9999 * 9998) / (3*2*1)이다.
즉 3중 반복문을 돌려야 해서 일반적인 탐색으로는 시간초과가 날 것이다.
그래서 다른 방법이 필요했다.
2개의 숫자 찾기
여기서 주목한 점은 골라야 하는 수가 3개로 고정이라는 점과
문제의 제한시간이 4초로 꽤나 길게 잡혔다는 점이다.
골라야 하는 수가 3개이기 때문에, 숫자 2개가 정해지면 나머지 하나는 자동적으로 확정된다.
이 점을 이용해서 문제를 풀 수 있을 것 같다.
그리고 제한시간이 N의 최대 범위가 10,000이고 제한시간 4초이다.
이것이 의미하는 바는,
이중 반복문을 통해 숫자 2개를 고르는 모든 경우의 수를 구하는 것 정도는 가능하다는 것
왜냐하면 10^4 * 10^4 = 10^8로 1초 미만으로,
이 탐색을 하고 다른 작업을 해도 충분히 시간이 남기 때문이다.
나머지 1개의 숫자 찾기
이제 남은 것은 나머지 1개의 숫자를 빠르게 찾는 것이다.
어떤 숫자인지는 알겠는데, 이를 어떻게 해야 빠르게 탐색해서 찾을 수 있을까?
이 문제는 정수만 쓰이기 때문에 흔히 떠올릴 수 있는 게 이분탐색이었다.
이분 탐색은 시간복잡도가 logN밖에 안되기 때문에
위에 숫자 2개를 찾는 것과 합쳐도 N*N*logN 이어서 4초가 넘지 않는다.
이분탐색을 사용해 주기 위해 모든 배열을 오름차순으로 정렬해 주고 탐색해준다.
고려해야 할 점은 숫자가 중복이 가능한데, 이것이 모두 다른 경우이다.
그래서 이분탐색을 통해 원하는 값을 낮은 인덱스부터 찾는 함수(lower_bound)와
원하는 값을 초과하는 인덱스를 찾는 함수(upper_bound)를 사용했다.
그래서 아래 그림처럼 작업을 했다.
이중 반복을 통해 -4와 2를 탐색하는 순서라고 가정하자.
이때 -4 + 2 = -2이다. 그리고 합이 0이 되기 위해서는 2가 되어야 한다.
그래서 lower_bound(2)와 upper_bound(2)를 선택한 인덱스보다 큰 인덱스에서 찾는다.
그럼 위와 같이 범위가 나오고 둘의 인덱스를 빼주면 개수가 나오게 된다.
이런 식으로 모든 개수를 찾으면 답이 나오게 된다.
이제 바로 문제 구현 단계로 가서 구현해 보자.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N;
vector<int> v(N);
for(int i = 0; i < N; i++) cin >> v[i];
sort(v.begin(),v.end()); // 오름차순 정렬
long long ans = 0; // 경우의 수가 int를 넘을 수 있음
// 이중 반복으로 2개의 값을 고름
for(int i = 0; i < v.size()-1; i++){
for(int j = i+1; j < v.size(); j++){
// 구해야할 나머지 1개의 값을 구함
long long cnt = v[i]+v[j];
// 개수 찾는 과정
int idx1 = lower_bound(v.begin()+j+1,v.end(),-cnt)-v.begin();
int idx2 = upper_bound(v.begin()+j+1,v.end(),-cnt)-v.begin();
ans += idx2 - idx1; // 구한 개수를 더함
}
}
cout << ans;
}코드는 굉장히 짧다.
upperbound와 lowerbound를 할 때 탐색 범위를
두 번째 골라준 인덱스 다음 값(j+1)부터 해주는 것에 유의하자.
코드들은 주석으로 다들 이해가 될 것인데,.
한 가지 주목해야 할 점은 출력값을 long long 자료형으로 해준 것이다.
이는 10000C3이기 때문에 경우의 수가 int형을 벗어날 가능성이 있기 때문이다.
여기까지가 모든 설명의 끝이고, 설명을 마치겠다
시행착오
처음에는 dp인가 싶다가, dp는 도저히 아닌 것 같아서 map을 써서 어떻게든 풀어보려고 했다.
근데 아무리 해도 중복 문제를 해결할 수가 없어서 포기했다.
나도 처음에는 3개 중 2개 고르면 1개가 정해진다는 것은 알았는데, 이것도 시간초과가 날 줄 알았지..
이분탐색을 하면 안 날 줄은 몰랐다. 덕분에 이분탐색 시간 복잡도가 logN이란건 안 까먹을 듯
왠지 모르게 이분탐색 문제는 알아차리가 가 쉽지가 않다.
여태껏 한 번도 알아차린 적이 없는 것 같다.
좀 알아차려보자.
생활비..