[백준 3151] 합이 0 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/3151

 

문제

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

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

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

 

입력

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

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

 

출력

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

풀이

접근법

1. 더해서 0이 되려면 plus + minus 여야 한다. 근데 총 3개의 숫자니까 plus2개 + minus1개 또는 plus1개 + minus2개 여야 한다.
2. 이걸 관리하기 위해서 배열을 생성해서 2개짜리 더했을 때 몇개가 나오는지 관리하자
   
   1. 처음에는 투포인터로 구할까 했었는데, 메모리도 그렇고 수도 더해야 20000이라 그냥 배열로 선언해주었다.
3. 그런 다음 plus랑 minus의 경우의 수를 다 더해주면 된다.
4. 0의 경우 3개를 더하면 그냥 0이 나오니까, 0의 개수를 따로 구해서 zeroC3(조합)으로 경우의 수를 더해주자.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        List<Integer> minusList = new ArrayList<>(N);
        List<Integer> plusList = new ArrayList<>(N);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int zero = 0;
        // 1. 더해서 0이 되려면 plus + minus 여야 한다. 근데 총 3개의 숫자니까 
        // plus2개 + minus1개 또는 plus1개 + minus2개 여야 한다.
        for(int i=0;i<N;i++) {
            int input = Integer.parseInt(st.nextToken());
            if (input == 0) zero++;
            if(input < 0) minusList.add(input * -1);
            else plusList.add(input);
        }
        // 2. 이걸 관리하기 위해서 배열을 생성해서 2개짜리 더했을 때 몇개가 나오는지 관리하자
        // 2-1. 처음에는 투포인터로 구할까 했었는데, 메모리도 그렇고 수도 더해야 20000이라 그냥 배열로 선언해주었다.
        int[] plusSum = new int[20001];
        int[] minusSum = new int[20001];
        for(int i=0;i<plusList.size();i++) {
            for(int j=i+1;j<plusList.size();j++) plusSum[plusList.get(i) + plusList.get(j)]++;
        }
        for(int i=0;i<minusList.size();i++) {
            for(int j=i+1;j<minusList.size();j++) minusSum[minusList.get(i) + minusList.get(j)]++;
        }
        long ans = 0;
        // 3. 그런 다음 plus랑 minus의 경우의 수를 다 더해주면 된다.
        for(int i=0;i<plusList.size();i++) ans += minusSum[plusList.get(i)];
        for(int i=0;i<minusList.size();i++) ans += plusSum[minusList.get(i)];
        if (zero >= 3) {
            // 4. 0의 경우 3개를 더하면 그냥 0이 나오니까, 0의 개수를 따로 구해서 zeroC3(조합)으로 경우의 수를 더해주자.
            long temp = zero * (long)(zero-1) * (zero-2);
            ans += temp/6;
        }
        System.out.println(ans);

    }
}

 

16분 걸렸다 ! zero 를 이용해서 zeroC3을 구하는데에 시간이 너무 오래걸렸다. Long 타입을 써야한다는 걸 까먹어서..ㅎ