백준 7453 - 합이 0인 네 정수(C++)

문제 링크입니다. https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

중간에서 만나기 방법을 사용하는 문제입니다.

배열 A, B, C, D에서 수를 한 개씩 뽑아 합이 0이 되게 만드는 문제입니다.

배열의 크기가 크기 때문에 모든 경우를 탐색하기에는 무리가 있습니다.

따라서, (A+B) / (C+D)로 나눠서 합을 구한 뒤, 둘을 합치는 방법을 사용합니다.

두 배열에 있는 수를 더하는 것이기에 합이 같은 경우가 있을 수 있습니다. 

따라서, lower_bound && upper_bound를 이용해 구하길 원하는 수가 어디서 시작되고 끝나는 지를 확인해줘야합니다.

그래야지 정확한 갯수를 구할 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>

using namespace std;

int N;
int A[4001], B[4001], C[4001], D[4001];
vector<long long> sum;

void solve() {
    long long ans = 0;
	for(int i = 0; i < N; i++){
	    for(int j = 0; j < N; j++){
	        sum.push_back(A[i] + B[j]);
	    }
	}
	sort(sum.begin(), sum.end());
	for(int i = 0; i < N; i++){
	    for(int j = 0; j < N; j++){
	        long long Sum = -(C[i] + D[j]);
	        long long low = lower_bound(sum.begin(), sum.end(), Sum) - sum.begin();
	        long long high = upper_bound(sum.begin(), sum.end(), Sum) - sum.begin();
	        if(Sum == sum[low]) ans += (high-low);
	    }
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; i++){
	    scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요