[백준 - 2632][Gold 2][해설 X] - 피자판매 (JAVA)

문제 링크

---

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

 

문제

---

고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다.

<그림 1>

고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다.

<그림 2>

피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로그램을 작성하시오

 

입력

---

첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n ≤ 1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기는 시계방향으로 차례로 주어지며, 각 피자 조각의 크기는 1000 이하의 자연수이다.

 

출력

---

첫째 줄에는 피자를 판매하는 방법의 가지 수를 나타내는 정수를 출력한다. 피자를 판매하는 방법이 없는 경우에는 숫자 0을 출력한다.

 

헤결 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.Map;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        Map<Integer,Integer> pizzaAPeiceCountMap = getPizzaPieceCountMap(m);	//피자 A의 모든 피자 조합
        Map<Integer,Integer> pizzaBPeiceCountMap = getPizzaPieceCountMap(n);	//피자 B의 모든 피자 조합

		//피자 A만 사용하는 경우와 B만 사용하는 경우 구하기
        int count = pizzaBPeiceCountMap.getOrDefault(N,0) + pizzaAPeiceCountMap.getOrDefault(N,0);

		//A와 B의 짝으로 목표 피자 사이즈가 되는 조합을 추가
        for(int size : pizzaAPeiceCountMap.keySet()){
            if(size >= N){
                continue;
            }

            count += pizzaAPeiceCountMap.get(size) * pizzaBPeiceCountMap.getOrDefault(N - size,0);
        }

        System.out.println(count);
    }

	//모든 피자 조합을 구하는 메소드
    public static Map<Integer,Integer> getPizzaPieceCountMap(int totalSize) throws IOException {
        //피자는 원이므로 링크드 리스트 형태이기 때문에 배열 크기를 2배로 설정
        int[] pizza = new int[totalSize*2];
        int sum = 0;
        
        for(int i=0;i<totalSize;i++){
            int size = Integer.parseInt(br.readLine());

            sum+=size;
            pizza[i] = size;
            pizza[i+totalSize] = size;
        }

        Map<Integer,Integer> pizzaPeiceCountMap = new HashMap<>();
        //모든 피자조각을 사용하는 경우 추가
        pizzaPeiceCountMap.put(sum,1);
        
		//누적합을 이용해 모든 연속된 조각의 경우의 수 구하기
        for(int i=0;i<totalSize;i++){
            sum = 0;
            for(int j=i;j<i+totalSize-1;j++){
                sum += pizza[j];
                pizzaPeiceCountMap.put(sum,pizzaPeiceCountMap.getOrDefault(sum,0)+1);
            }
        }

        return pizzaPeiceCountMap;
    }
}

 

 

실행 결과

---