[백준]3151: 합이0(java)

https://www.acmicpc.net/problem/3151

3151번: 합이 0

문제

Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.

Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.

N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.

입력

입력은 표준 입력으로 주어진다.

첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.

출력

표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.

제한

• 1 ≤ N ≤ 10000
• -10000 ≤ Ai ≤ 10000

예제 입력 1

10
2 -5 2 3 -4 7 -4 0 1 -6

예제 출력 1

6

---

풀이

이분탐색을 사용하기 위해 정렬했습니다.

하나의 단어를 고정하고 나머지 두 단어를 이분탐색을 통해 찾습니다.

만약 0 0 0 0 0 으로 0을 만드는 경우는

5C3 입니다. 하지만 우리는 1개를 고정하기때문에 0 / 0 0 0 0 이므로 4C2만 하면 되는 것을 알 수 있습니다.

이처럼 경우의수를 잘 생각해야 하는게 힘들었던 문제였습니다.

다른 예로

10
-1 -1 0 0 0 1 1 1 1 1

라면

처음 -1을 fix합니다.

그 후

left : -1 right : 1 이므로 sum=-1이 됩니다. sum < 0 이므로 left++이 수행됩니다.

left : 0 right : 1 이므로 sum = 0 이 됩니다.

하지만 여기서 주의해야합니다.

앞으로 0은 left기준 본인 포함 3개, 1은 right 기준 본인 포함 5개 입니다.

그렇다면 고정한 -1은 0 3개, 1 5개를 고르는 경우의 수인 3 * 5 = 15개의 0을 만들 수 있습니다.

전체 코드

package 백준;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_G5_3151_합이0 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[]arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        long cnt = 0;
        for(int i=0; i<N; i++) {
            if(arr[i] > 0) break;
            int num = arr[i];
            int left = i+1;
            int right = N-1;

            while(left < right) {
                int sum = num + arr[left] + arr[right];

                if(sum == 0) {
                    int l = 1;
                    int r = 1;
                    if(arr[left] == arr[right]) {
                        int n = right-left+1;
                        cnt += Combination(n);
                        break;
                    }
                    while (arr[left] == arr[left + 1]) {
                        l++;
                        left++;
                    }
                    while (arr[right] == arr[right - 1]) {
                        r++;
                        right--;
                    }

                    cnt+= l * r;
                }

                if(sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        System.out.println(cnt);
    }

    public static long Combination(int n) {
        return n * (n - 1) / 2;
    }
}