[JAVA] 2632 - 피자판매 💛2 : 값이 아닌 경우의 수를 저장하자. + 원형 자료구조는 선형 자료구조로 피자!

들어가며

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

A피자와 B피자가 여러 크기를 가진 여러 조각으로 나누어져있다. 이때 구매자가 원하는 N의 값을 만족하는 피자를 A에서 혹은 B에서 혹은 A,B에서 가져올 수 있다. 그때 구할 수 있는 모든 경우의 수를 구하면 되는 문제이다.

본문으로

정석적인 풀이는 모든 합의 경우의 수를 구하면 되지 않을까란 생각이 듦과 동시에 그러면 안된다는 생각이 들어야한다 ㅎㅎ. 그러면 정렬 후 투포인터로 하나씩 고르면 되지 않을까 싶은데,, 문제에서 "2조각 이상 판매할 때는 연속된 피자를 골라야한다" 라고 명시되어 있다. 이 조건 하나때문에 투포인터로 구현하기가 매우 어려워진다.

 

생각을 이어나가다 보면 각 피자의 값을 하나씩 고르는 방식으로는 구현이 너무너무 어려워진다. 여기서 A, B, A+B 의 모든 경우의 수를 구하면 되지 않을까?(누적합)으로 생각이 이어진다. 아래는 누적합으로 모든 합의 경우의 수를 구해놓은 다음 사용자가 원하는 값을 만족하는 경우의 수만 구해준 방식으로 구현한 정답 코드이다.

public class Main {

    static int want, m, n, ret;
    static int[] a, b;
    static int[] pSumA, pSumB;
    static Map<Integer, Integer> aCnt = new HashMap<>();
    static Map<Integer, Integer> bCnt = new HashMap<>();

    static void make(int n, int[] pSum, Map<Integer, Integer> map) {
        for (int interval = 1; interval <= n; interval++) {
            for (int start = interval; start <= n + interval - 1; start++) {
                int sum = pSum[start] - pSum[start - interval];
                map.put(sum, map.getOrDefault(sum, 0) + 1);

				// 전체 피자 한 판은 1번만
                if (interval == n) {
                    break;
                }
            }
        }

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        want = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        a = new int[n + 1];
        b = new int[m + 1];
        pSumA = new int[2 * n + 1];
        pSumB = new int[2 * m + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(br.readLine());
            pSumA[i] = pSumA[i - 1] + a[i];
        }
        // 2 2 2 7 8 5 + 2 2 2 7 8 5  -> 원형을 선형처럼
        for (int i = n + 1; i <= 2 * n; i++) {
            pSumA[i] = pSumA[i - 1] + a[i - n];
        }

        for (int i = 1; i <= m; i++) {
            b[i] = Integer.parseInt(br.readLine());
            pSumB[i] = pSumB[i - 1] + b[i];
        }

        for (int i = m + 1; i <= 2 * m; i++) {
            pSumB[i] = pSumB[i - 1] + b[i - m];
        }

        make(n, pSumA, aCnt);
        make(m, pSumB, bCnt);

        int ret = aCnt.getOrDefault(want, 0) + bCnt.getOrDefault(want, 0);

        for (int i = 1; i < want; i++) {
            ret += aCnt.getOrDefault(i, 0) * bCnt.getOrDefault(want - i, 0);
        }

        System.out.println(ret);

    }
}

특히 구간합을 구하는 부분을 보면 범위를 두배 해서 구해주는 것을 볼 수 있는데, 이게 원형 자료구조의 구간합을 구현하려면 해보면 알겠지만 매우 복잡해진다. 그럴 때는 뒤로 이어주는 식으로 해서 선형자료구조로 만들어준다면 비교적 쉽게 구간합을 구할 수 있어진다.

// 피자 한판
2 2 7 8 5

// 원형 자료구조를 선형 자료구조로
2 2 7 8 5 + 2 2 7 8 5

마무리하며

솔직히 문제 많이 어려웠다. 특히 구간합을 구할때 원형자료구조를 선형으로 이어준다는 점이 떠올리기 어려운 문제였다고 생각한다. 어우 그리고 구간합을 활용한 문제 오랜만에 풀어보는데 인덱스 관련된 부분때문에 헷갈려 죽는줄 알았다!
구간합은 선형 자료구조에서 시간복잡도를 줄일 수 있는 유명한 놈이므로 더욱 더 친숙해지자!