[백준]2632: 피자판매 - JAVA

[백준]2632: 피자판매

2632번: 피자판매

풀이

🪑 손님이 원하는 크기의 피자만큼 판매할 수 있는 경우의 수를 계산하는 문제로 다양한 풀이 방법이 존재하는 문제이다.

 

먼저 문제의 조건 부터 정리해 보자.

• A, B의 피자는 다양한 크기의 여러 조각으로 나누어져 있다.
• 한 종류의 피자를 2조각 이상 판매시 연속된 조각으로 잘라 판매하며 피자 조각의 크기 합이 주문한 크기가 되어야 한다.
• 판매한 피자 조각는 A조각으로만 이루어 질 수 있고, B조각으로만 이루어 질 수 있고, A와 B조각 으로 이루어 질 수 도 있다.
• 손님이 원하는 크기의 피자를 판매할 수 있는 모든 방법의 수를 알아야 한다.

 

 

🤔 처음에는 이분탐색으로 풀려고 하였다.

- 기준값을 판매할 수 있는 조각으로 두고 범위를 0 부터 최대값으로 설정해 주었었다.

- mid만큼 판매할 수 있는지 확인하여 판매할 수 있다면 더 큰값을, 판매할 수 없다면 더 작은값을 탐색하도록 하였다.

 

🙋‍♀️ 그러나 이 문제에서 mid조각 만큼 판매할 수 있는지 확인하는 과정에서 중복되는 연산이 발생한다.

- 만약 3개의 조각만큼 판매할 수 있는지 확인하는 과정을 거쳐 다음에는 5개의 조각으로 판매할 수 있는지 확인해 본다고 생각해 보면, 5개의 조각으로 판매할 수 있는지 확인하는 과정 안에 3개의 조각으로 판매할 수 있는지 계산하는 과정이 포함된다. (3개 선택시 선택하는 피자 조각의 개수 확인은 1 ~ 3만큼 이뤄지고, 5개 선택시 선택하는 피자 조각의 개수 확인은 1 ~ 5만큼 이뤄지게 된다.)

- 이런 식으로 이분탐색을 하면 계속 중복 계산이 발생하게 되고 불필요한 연산이라는 생각이 들었다.

- 그래서 미리 size만큼 n개의 조각을 사용하여 판매할 수 있는 개수를 계산해 주어서 불필요한 계산을 없애야 겠다는 생각이 들었다. 

- 위 방법대로 연산해 준다면 이분탐색을 굳이 할 필요가 없어진다. 

 

 

🔧 그래서, 나는 다음과 같이 풀었다.

1. A, B 피자를 입력 받고 하나도 선택하지 않았을 경우, 최대로 선택했을 경우의 개수를 초기화 해준다.
2. A 피자에서 선택하는 피자 조각의 개수에 따른 크기의 합을 계산해 주었다. 이때 같은 합을 같는 피자 조각을 카운트 해 주었다.
3. B 피자에서 선택하는 피자 조각의 개수에 따른 크기의 합을 계산해 주었다. 이때 같은 합을 같는 피자 조각을 카운트 해 주었다.
4. 손님이 원하는 크기만큼 만들 수 있는 피자 조각의 조합을 계산해 주었다.

 

 

🔹 개수를 초기화 해준다.

- 피자 조각을 하나도 선택하지 않았을 때와 모든 피자 조각을 선택했을 때의 경우는 한가지 밖에 없으므로 해당 값을 1로 초기화 해 주었다.

- 모든 피자 조각을 선택했을 때를 알기 위해 입력받는 피자 값의 합을 따로 저장해 주었다.

 

🔹 피자 조각의 개수에 따른 크기의 합을 계산해 주었다.

- 시작하는 피자의 인덱스 값을 바꿔가며 해당 위치에서 피자 조각을 (1 ~ 전체 피자조각 - 1)만큼 까지 선택하며 모든 경우의 수를 구해주었다.

- 이때 피자 조각의 합이 손님이 원하는 크기보다 크다면 그 이후로는 연속해서 피자조각을 선택할 필요가 없으므로 break해 주었다.

- 선택하는 피자조각의 개수 만큼 현재 인덱스의 피자 값에 누적하여 더하며 나올 수 있는 크기의 합의 카운트를 하나씩 올려 주었다.

- 이때 count배열이 의미하는 값은 인덱스의 크기 만큼 만들 수 있는 피자 조각의 조합이 수가 된다.

 

🔹 손님이 원하는 크기만큼 만들 수 있는 피자 조각의 조합을 계산해 준다.

- 이제 A, B로 만들 수 있는 모든 피자조각의 경우의 수를 카운트 해 주었다.

- 우리가 원하는 값은 size만큼 만들 수 있는 피자 조각의 경우의 수이다.

- 그러므로 (0 ~ size) 만큼 탐색하여 A, B 조각의 경우의 수의 합이 size가 되는 경우 각각의 경우의 수 끼리 곱한 값을 누적하면 원하는 답을 구할 수 있다. 

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        int size = scan.nextInt();
        int a = scan.nextInt();
        int b = scan.nextInt();
        
        int[] a_pizza = new int[a];
        int max_a = 0;
        for(int i = 0; i < a; i++) {
            a_pizza[i] = scan.nextInt();
            max_a += a_pizza[i];
        }
 
        int[] b_pizza = new int[b];
        int max_b = 0;
        for(int i = 0; i < b; i++) {
            b_pizza[i] = scan.nextInt();
            max_b += b_pizza[i];
        }
        //입력 끝!
 
        int[] a_count = new int[Math.max(max_a, size) + 1];
        a_count[0] = 1;
        a_count[max_a] = 1;
        count(a_pizza, a_count, size);
 
        int[] b_count = new int[Math.max(max_b, size) + 1];
        b_count[0] = 1;
        b_count[max_b] = 1;
        count(b_pizza, b_count, size);
 
        int result = 0;
        for(int i = 0; i <= size; i++) {
            result += (a_count[i] * b_count[size - i]);
        }
        System.out.println(result);
    }
 
    public static void count(int[] pizza, int[] count, int size) {
        for(int i = 0; i < pizza.length; i++) { //시작하는 피자의 인덱스
            int sum = 0;
            for(int j = 1; j < pizza.length; j++) { //선택하는 피자 조각의 개수
                int sum_j = pizza[(i + j) % pizza.length];
                if(sum + sum_j > size) break;
                sum += sum_j;
                count[sum]++;
            }
        }
    }
}