7453

합이 0인 네 정수 : https://www.acmicpc.net/problem/7453

참조 : https://loosie.tistory.com/553

 

문제 풀이가 안되어 참조 포스팅의 내용을 스터디할 목적으로 작성된 코드.

이번에도 배열을 두개로 나누어 부분합을 구함( a와b를 1:1 , b와c를 1:1)

N*N => 4000*4000으로 int로 넉넉함.

 

입력값이 2^28로 4개 요소를 더하면 overflow 발생.

값을 연산하기 위해 long으로 사용해야한다.

 

cnt의 경우도 N^4까지 발생할 수 있으므로 long을 취해야한다.

cnt계산 시 중복을 처리하는 방법을 생각해낸 사람은 정말 대단한 것 같다.

 

//refer : https://loosie.tistory.com/553
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N;
	static int[][] abcd;
	static int[] ab, cd;
	static boolean DBG = false;


	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		abcd = new int[N][4];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < 4; j++) {
				abcd[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		ab = new int[N * N];// 1:1 matching
		cd = new int[N * N];// 1:1 matching

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ab[i * N + j] = abcd[i][0] + abcd[j][1];
				cd[i * N + j] = abcd[i][2] + abcd[j][3];
			}
		}

		Arrays.sort(ab);
		Arrays.sort(cd);

		if (DBG) {
			for (int v : ab)
				System.out.print(v + " ");
			System.out.println();
			for (int v : cd)
				System.out.print(v + " ");
			System.out.println();
		}
		
		int abp=0,cdp=N*N-1;
		long cnt =0;
		
		while (abp <N*N && cdp>-1) {

			
			long abv = ab[abp], cdv=cd[cdp];
			long sum=abv+cdv;
			if( sum < 0) {
				abp++;
			} else if( sum > 0) {
				cdp--;
			} else {
				
				long abCnt=0,cdCnt=0;
				
				while(abp<N*N && abv == ab[abp]) {
					abp++;
					abCnt++;
				}
				while(cdp>-1 && cdv == cd[cdp]) {
					cdp--;
					cdCnt++;
				}
				
				cnt += abCnt * cdCnt;
				
				//System.out.printf("cnt : %d\n",cnt);
			}
			
		}
		System.out.println(cnt);
		
		
	}

}

 

 

아래와 같이 two points 로만 탐색하면 중복에 대한 처리가 제대로 카운팅되지 않는다.

같은 값의 요소들은 서로 1:1로 매핑되어 세어줘야한다.

		while (abp <N*N && cdp>-1) {

			
			int abv = ab[abp], cdv=cd[cdp];
			long sum=abv+cdv;
			if( sum < 0) {
				abp++;
			} else if( sum > 0) {
				cdp--;
			} else {
				cnt++;
				abp++;
				//System.out.printf("cnt : %d\n",cnt);
			}
			
		}