백준 2632 피자 판매

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

2632번: 피자판매

 

구현하는 문제!

 

A피자에서 나올 수 있는 모든 경우의 합을 저장하고

 

B피자에서 나올 수 있는 모든 경우의 합을 저장 한 후

 

각각의 합을 비교해가면 된다. 

 

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int count, N, A, B;
    static List<Integer> listA = new ArrayList<>();
    static List<Integer> listB = new ArrayList<>();

    static int pI(String s) {
        return Integer.parseInt(s);
    }

    static void b_t(int cnt, int index, int sum, List<Integer> list, List<Integer> target) {
        if (sum != 0)
            target.add(sum);
        if (cnt == list.size() / 2 - 1) {
            return;
        }

        b_t(cnt + 1, index + 1, sum + list.get(index), list, target);
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = pI(st.nextToken());

        st = new StringTokenizer(br.readLine());
        A = pI(st.nextToken());
        B = pI(st.nextToken());

        List<Integer> inputA = new ArrayList<>();
        List<Integer> inputB = new ArrayList<>();

        for (int i = 0; i < A; i++) {
            inputA.add(pI(new StringTokenizer(br.readLine()).nextToken()));
        }

        for (int i = 0; i < B; i++) {
            inputB.add(pI(new StringTokenizer(br.readLine()).nextToken()));
        }

        List<Integer> sumA = new ArrayList<>();
        List<Integer> sumB = new ArrayList<>();

        inputA.addAll(inputA);
        inputB.addAll(inputB);
        int cnt = 0;
        for (int i = 0; i < inputA.size() / 2; i++) {
            b_t(0, i, 0, inputA, sumA);
            cnt += inputA.get(i);
        }
        sumA.add(cnt);
        cnt = 0;
        for (int i = 0; i < inputB.size() / 2; i++) {
            b_t(0, i, 0, inputB, sumB);
            cnt += inputB.get(i);
        }
        sumB.add(cnt);

        Collections.sort(sumA);
        Collections.sort(sumB, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });

        count += (int) sumA.stream().filter(s -> s == N).count() + (int) sumB.stream().filter(s -> s == N).count();
        int indexA = 0, indexB = 0;
        while (indexA < sumA.size() && indexB < sumB.size()) {
            int temp = sumA.get(indexA) + sumB.get(indexB);
            if (temp == N) {
                int ii = 1, jj = 1;
                indexA++;
                indexB++;
                while (indexA < sumA.size() && sumA.get(indexA).equals(sumA.get(indexA - 1)) ) {
                    ii++;
                    indexA++;
                }

                while (indexB < sumB.size() && sumB.get(indexB).equals(sumB.get(indexB - 1)) ) {
                    jj++;
                    indexB++;
                }

                count += ii * jj;
            } else if (temp > N) {
                indexB++;
            } else if (temp < N) {
                indexA++;
            }
        }
        bw.write(count + "\n");
        bw.flush();
    }
}