[백준 7453] 합이 0인 네 정수

 

A, B, C, D 배열의 각각을 더해서 0과 비교하기에는 시간이 너무 오래걸린다.

 

1. A, B의 모든 부분합을 저장한 배열을 만든다. (C, D의 부분합 배열이어도 상관없다.)

2. C, D의 모든 부분합을 저장한 Map을 만든다. 부분합 중 중복된 수가 있다면 카운트를 올린다.

   Map의 Key를 sum, Value를 카운트로 사용했다.

3. A, B의 부분합 배열과 Map의 원소들을 비교하며 두 원소의 합이 0일 경우 카운트만큼 개수를 올린다.

 

코드는 알아보기 꽤나 쉽다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int temp[][] = new int[n][4];
        for(int i=0; i<n; i++) {
            temp[i][0] = sc.nextInt();
            temp[i][1] = sc.nextInt();
            temp[i][2] = sc.nextInt();
            temp[i][3] = sc.nextInt();
        }
        
        int a[] = new int[n*n];
        Map<Integer, Integer> b = new HashMap<Integer, Integer>();
        int idx = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                a[idx++] = temp[i][0] + temp[j][1];
                int sum = temp[i][2] + temp[j][3];
                if(b.containsKey(sum)) b.put(sum, b.get(sum) + 1);
                else b.put(sum, 1);
            }
        }
        
        long result = 0;
        for(int i=0; i<n*n; i++) {
            int key = -a[i];
            if(b.containsKey(key))
                result += b.get(key);
        }
        System.out.println(result);
    }
}