[백준]2632번. 피자 판매(JAVA)

문제

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

---

풀이

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

public class Main {

    static int quiz;
    static int n, m;
    static int[] pizzaA, pizzaB;
    static int[] sumA = new int[2000001];
    static int[] sumB = new int[2000001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        quiz = Integer.parseInt(br.readLine()); // N값 (퀴즈 점수)
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 피자 A의 조각 개수
        m = Integer.parseInt(st.nextToken()); // 피자 B의 조각 개수

        pizzaA = new int[n * 2]; // 원형 배열을 위한 두 배 크기
        pizzaB = new int[m * 2]; // 원형 배열을 위한 두 배 크기

        // 피자 A 입력 및 원형 배열 확장
        int totalSumA = 0;
        for (int i = 0; i < n; i++) {
            pizzaA[i] = Integer.parseInt(br.readLine());
            pizzaA[i + n] = pizzaA[i]; // 원형 배열 구현
            totalSumA += pizzaA[i];
        }
        sumA[0] = 1; // 빈 피자도 선택 가능
        sumA[totalSumA] = 1; // 피자 A 전체 합도 저장

        // 피자 B 입력 및 원형 배열 확장
        int totalSumB = 0;
        for (int i = 0; i < m; i++) {
            pizzaB[i] = Integer.parseInt(br.readLine());
            pizzaB[i + m] = pizzaB[i]; // 원형 배열 구현
            totalSumB += pizzaB[i];
        }
        sumB[0] = 1; // 빈 피자도 선택 가능
        sumB[totalSumB] = 1; // 피자 B 전체 합도 저장

        // 피자 A의 부분합 개수 구하기
        funSumCnt(n, pizzaA, sumA);

        // 피자 B의 부분합 개수 구하기
        funSumCnt(m, pizzaB, sumB);

        // 최종 정답 계산
        int answer = 0;
        for (int i = 0; i <= quiz; i++) {
            answer += sumA[i] * sumB[quiz - i]; // 두 부분합이 quiz와 일치하는 경우를 곱함
        }

        System.out.println(answer);
    }

    // 부분합 계산 함수
    private static void funSumCnt(int c, int[] arr, int[] sumCnt) {
        for (int i = 0; i < c; i++) {
            int sum = 0;
            for (int j = i; j < i + c - 1; j++) {
                sum += arr[j];
                if (sum > quiz) break; // sum이 quiz를 초과하면 멈춤
                sumCnt[sum]++;
            }
        }
    }
}

 

문제를 해결하는 방법 자체보다 개념적인 접근이 필요한 문제였다.

결과적으로 경우의 수로 구하면 되는 문제로 간단하다고 볼 수 있다. 이에 대해 직접 카운트를 하는 것이 아닌 부분합 배열을 따로 선언해둬 이를 이용한다.

또한, 원형배열을 사용하기위해 배열을 두배로 확장하는 스킬을 사용했다.