백준_합이0인네정수_7453

문제 링크

조건

• n개의 배열 4개(A, B, C, D) : 1 <= n <= 4000

 

접근 방법

• 완전탐색 시 4000^4 이기 때문에 시간초과남
• (A, B) & (C, D) 두 개씩 묶음
  • 4000 * 4000 = 16,000,000 => 시간, 공간 초과 X
  • 각 묶음에서 나올 수 있는 부분합 경우의 수를 sumA, sumB 배열에 저장 (sumA, sumB = new int[n*n])
  • sumA, sumB 오름차순 정렬
  • sumA 값과 대응되는 값(합이 0이 되는)을 sumB에서 이분탐색
    • 이분탐색 시 중복된 값 개수 체크하기 위해 lower, upper bound 활용
• 모든 경우의 합은 int 범위를 넘길 수 있음 => ans변수 long 타입 선언

 

솔루션

public class Main {
	
	static int n;//배열 크기
	static int[][] num;
	static int[] sumA, sumB;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine().trim());
		
		num = new int[4][n];
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j = 0; j < 4; j++) {
				num[j][i] = Integer.parseInt(st.nextToken());
			}
		}
		
		sumA = new int[n*n];
		for(int i = 0, idx = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				sumA[idx++] = num[0][i] + num[1][j];
			}
		}
		Arrays.sort(sumA);//부분합 집합 정렬
		
		sumB = new int[n*n];
		for(int i = 0, idx = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				sumB[idx++] = num[2][i] + num[3][j];
			}
		}
		Arrays.sort(sumB);부분합 집합 정렬
		
		long ans = 0;
		for(int i = 0; i < n*n; i++) {
			int cur = sumA[i];
			
			int al = lower(cur, sumA);
			int au = upper(cur, sumA);
			
			i = au-1;
			
			int bl = lower(-cur, sumB);
			if(bl == -1) continue;
			int bu = upper(-cur, sumB);
			
			ans += (long)(au-al) * (bu-bl);
		}
		
		System.out.println(ans);
	}
	
    //sum 배열에서 최초로 cur 보다 큰 값이 나오는 idx 리턴 ( 없으면 -1 )
	private static int upper(int cur, int[] sum) {
		int s = 0, e = sum.length-1;
		int m = 0;
		int idx = -1;
		
		while(s <= e) {
			m = (s+e)/2;
			
			if(sum[m] > cur) {
				e = m-1;
			}else {
				if(sum[m] == cur) idx = m;
				s = m+1;
			}
		}
		return idx == -1 ? -1 : idx+1;
	}
	
    //sum 배열에서 최초로 cur값 나오는 idx 리턴 ( 없으면 -1 )
	private static int lower(int cur, int[] sum) {
		int s = 0, e = sum.length-1;
		int m = 0;
		int idx = -1;
		
		while(s <= e) {
			m = (s+e)/2;
			
			if(sum[m] < cur) {
				s = m+1;
			}else {
				if(sum[m] == cur) idx = m;
				e = m-1;
			}
		}
		return idx;
	}
}

 

리뷰

• 4개의 배열을 둘 씩 묶어야겠다는 생각까지는 했지만, 이분탐색 아이디어는 생각 못함
• 완탐을 하기에 범위가 지나치게 큰 경우, 그리디나 이분탐색 등 시간을 줄일 수 있는 로직쪽으로 생각해볼 것
• 항상 답을 구하는 과정에서 int 타입 범위를 넘는지 체크해볼 것