[백준] 2632 피자 판매 java

import java.io.*;
import java.util.*;

public class SalePizza {
    static BufferedReader br;
    static StringTokenizer st;
    static int orderNum, m, n, ans;
    static int[] mPizzaPieces, nPizzaPieces;
    static List<Integer> left, right;

    public static void main(String[] args) throws IOException{
        /*
        1. 피자 A의 부분합을 구한다.
        2. 피자 B의 부분합을 구한다.
        3. 두 배열의 합 중 정답과 일치하는 것을 고른다.
        유의할 점은 피자는 원형이기 때문에 부분합을 구할 때 신경써준다.
         */
        input();
        getSubSequences();
        Collections.sort(left);
        Collections.sort(right);
        getSum();
        System.out.println(ans);
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        orderNum = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        mPizzaPieces = new int[m];
        nPizzaPieces = new int[n];
        left = new ArrayList<>();
        right = new ArrayList<>();
        left.add(0);
        right.add(0);
        for(int i = 0; i < m; i++) {
            mPizzaPieces[i] = Integer.parseInt(br.readLine());
        }
        for(int i = 0; i < n; i++) {
            nPizzaPieces[i] = Integer.parseInt(br.readLine());
        }
    }

    static void getSubSequences() {
        for(int i = 0; i < m; i++) {
            boolean[] checked = new boolean[m];
            checked[i]= true;
            calculate(mPizzaPieces, left, checked, mPizzaPieces[i], i, i+1);
        }
        for(int i = 0; i < n; i++) {
            boolean[] checked = new boolean[n];
            checked[i]= true;
            calculate(nPizzaPieces, right, checked, nPizzaPieces[i], i, i+1);
        }
    }

    static void calculate(int[] arr, List<Integer> list, boolean[] checked, int sum, int startIdx, int idx) {
        if(idx == arr.length) idx = 0;
        list.add(sum);
        //아직 방문하지 않았고 합이 orderNum보다 크지 않아야 하고 idx가 시작점을 넘지 않았어야 한다.
        if(!checked[idx] && sum + arr[idx] <= orderNum && idx != startIdx-1) {
            checked[idx] = true;
            calculate(arr, list, checked, sum+arr[idx], startIdx, idx+1);
        }
        else return;
    }

    static void getSum() {
        int start = 0;
        int end = right.size() - 1;
        while(start < left.size() && end >= 0) {
            int leftVal = left.get(start);
            int rightVal = right.get(end);
            int sum = leftVal + rightVal;
            if(sum == orderNum) {
                int leftCnt = 0;
                while(start < left.size() && left.get(start) == leftVal) {
                    start++;
                    leftCnt++;
                }
                int rightCnt = 0;
                while(end >= 0 && right.get(end) == rightVal) {
                    rightCnt++;
                    end--;
                }
                ans += leftCnt * rightCnt;
            }
            if(sum < orderNum) start++;
            if(sum > orderNum) end--;
        }
    }
}

이 문제 역시 두 배열의 부분합을 구해서 투포인터 알고리즘을 이용해 푸는 문제였다.

 

1. 피자 a의 부분합, 피자 b의 부분합을 구한다.

 

2. 두 리스트를 오름차순 정렬해준다.

 

3. 투포인터를 이용해서 하나는 left의 시작 하나는 right의 마지막에서 하나씩 더해가며 답을 구해준다.

 

이 문제에서 유의해야 할 점은 순환하는 배열이기 때문에 배열의 방문 체크와 인덱스 관리 (마지막 조각과 처음 조각이 이어질 수 있기 때문에), 한 피자에서 모든 조각을 담는 경우는 한번이기 때문에 중복돼서 담기지 않게 마지막 조각은 담지 않게 해주는 것도 중요하다. (idx < startIdx - 1 해주지 않으면 모든 조각을 담는 경우의 수가 원소의 갯수만큼 들어가게 됨.)