
b7453. 합이 0인 네정수
·
Algorithm & Data Structures/BOJ
https://www.acmicpc.net/problem/7453 4 개의 배열 a,b,c,d 가 있을 때 N개의 원소의합이 0이되는 조합의 수를 찾는 문제다.N의 범위가 4000 즉 4000*4000*4000*4000 을 하게되면 쉽게 풀수 있으나시간복잡도 측면에서 시간초과가 날것이 분명하기에풀이방법을 이분탐색을 이용하여 A,B의 배열에서 가능한 조합 16000000개와 C,D의 배열에서 가능한 더한 조합 16000000개를 만들어 두조합의 합이 0이되는경우를세기로 하였다. AB의 배열에서가능한 조합 A와 CD의 배열에서 가능한 조합 B를 순회돌기전 정렬을 통해 A,B배열을 오름차순으로 정렬하고 A의 원소중 -31,-31,-31 처럼 중복되는 경우가 생기면 이를 upperbound lowerboun..