[백준 알고리즘]2632번(피자판매)

백준 알고리즘

(2632번)피자판매

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1330	444	313	35.129%

문제

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

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

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

입력

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

출력

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

예제 입력 1

7
5 3
2
2
1
7
2
6
8
3

예제 출력 1

5

A, B두 부분집합을 각각 구한 후 목표값이 얼마나 존재하는지 세면 되는 문제이다. 기존에 사용하던 방식과 마찬가지로, 배열에 부분수열의 합들을 저장해 둔 뒤, 정렬하고, A 리스트의 왼쪽 인덱스부터, B리스트의 오른쪽리스트부터 순차 검색하여 count를 해주면 되는데, 해당 문제는 몇가지 조건들이 있기 때문에 신경써주어야 한다.

1. 연속된 조각들만 판매한다는점
2. 원판(피자) 이기때문에 마지막 배열 조각이 첫째 배열조각과 연결된다는 점

때문에 부분수열의 합을 생성할때 위의 조건을 고려한 수식을 작성해야한다. 특히나 마지막 배열 조각이 첫번째 배열 조각과 연결된다는 점은 순환큐를 구현하는데 사용한 인덱스 변경방식과 비슷하다고 생각이되었다. 부분수열의 합 부분을 위한 코드는 다음과 같다.

 //순환 큐 구현하듯이
public static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, List list) {
        if (idx == arr.length) idx = 0;

        list.add(sum);

        // 아직 안 담은 피자조각에 대해서만 판매하겠음 && 마지막 인덱스값을 계속 저장하지 않음 && 순열의 합이 이미 타겟을 넘어서면 계산하지않음
        if (check[idx] == false && idx != startIdx - 1 && sum <= target) {
            check[idx] = true;
            getSum(sum + arr[idx], startIdx, idx + 1, check, arr, list);
        } else { return; }
}

ㅇ배열의 마지막 인덱스가 될경우 idx 를 0으로 세팅해주고 있으며, 순간의 합을 바로 리스트에 추가한다.

check배열을 통해 이미 판매한 경우의 피자인지 아닌지를 판단하며,

얼핏 check[idx] == false 조건과 idx != startIdx-1 조건이 서로 똑같은것이 아닌지 오해할 수 있지만, 해당 조건이 없을경우 피자 전체의 합을 연산하는 경우의 수가 원소 개수만큼 반복되기 때문에 추가 되어야한다.

( startIdx 가 0일경우 -1과 같을 경우가 한번 생기기 때문에 전체 합을 생각하는 경우의 수가 추가된다)

위의 조건을 사용하지 않을 경우, 2, 2, 1, 7 , 2 배열의 연산이 리스트에 쌓이는 단계는 다음과 같다

2->4->5->12->14

2->3->10->12->14

1->8->10->12->14

...

하지만 피자 전체를 모든 원소 갯수만큼 추가되는것은 의도한 방향이 아니므로 해당 조건을 추가해서 디버깅을 하면 다음과 같이 리스트에 추가가 된다.

2->4->5->12->14

2->3->10->12

1->8->10->12

7->9->11->13

...

이를 통해 전체 결과가 지속적으로 추가되는 부분을 해결할 수 있었다. 다음은 전체 코드이다.

package baekjoon.chapter8;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Question2632 {


    static int target;
    static int m;
    static int n;
    static int[] A;
    static int[] B;
    static boolean[] check;
    static ArrayList<Integer> AList = new ArrayList<>();
    static ArrayList<Integer> BList = new ArrayList<>();
    static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        target = sc.nextInt();
        m = sc.nextInt();
        n = sc.nextInt();

        A = new int[m];
        B = new int[n];

        for (int i = 0; i < m; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            B[i] = sc.nextInt();
        }

        for (int i = 0; i < m; i++) {
            //체크 배열 초기화
            check = new boolean[m];
            //첫번째 조각 담기
            check[i] = true;
            getSum(A[i], i, i + 1, check, A, AList);
        }

        for (int i = 0; i < n; i++) {
            //체크 배열 초기화
            check = new boolean[n];
            //첫번째 조각 담기
            check[i] = true;
            getSum(B[i], i, i + 1, check, B, BList);
        }

        //각각 전혀 사용되지 않을 경우도 있으므로
        AList.add(0);
        BList.add(0);

        Collections.sort(AList);
        Collections.sort(BList);

        int leftIdx = 0;
        int rightIdx = BList.size() - 1;

        while (leftIdx < AList.size() && rightIdx >= 0) {
            int lv = AList.get(leftIdx);
            int rv = BList.get(rightIdx);

            if (lv + rv == target) {
                int lc = 0;
                int rc = 0;

                while (leftIdx < AList.size() && AList.get(leftIdx) == lv) {
                    lc++;
                    leftIdx++;
                }
                while (rightIdx >= 0 && BList.get(rightIdx) == rv) {
                    rc++;
                    rightIdx--;
                }

                ans += lc * rc;
            }

            if(lv + rv > target) rightIdx--;
            if(lv + rv < target) leftIdx++;

        }

        System.out.println(ans);


    }

    //순환 큐 구현하듯이
    public static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, List list) {
        if (idx == arr.length) idx = 0;

        list.add(sum);

        // 아직 안 담은 피자조각에 대해서만 && 순환 방지
        if (check[idx] == false && sum <= target && idx != startIdx - 1) {
            check[idx] = true;
            getSum(sum + arr[idx], startIdx, idx + 1, check, arr, list);
        } else { return; }
    }
}