2632 - 피자판매

문제: boj.kr/2632
날짜: 08/25 (일)
성공여부: X

 

이 문제 너무 어려웠다.

 

처음으로 생각해낸 로직은 그냥 무식하게 모든 경우의 수 구해서 원하는 값 되는 거 찾으면 되지 않을까? 하고 문제 범위를 봤는데, 3 <= m, n <= 1000이다. 1000C1, 1000C2, 1000C3 .... 이걸 A, B 두 번 구해서 A, B에 대해 다 for문 돌린다면 무조건 시간 초과날 것이 뻔했음..

 

근데 이거 아니면 아무 로직도 생각나지 않아서 해설 봤다. 정리하면 다음과 같은 로직으로 구성된다.

 

1. 원형을 선형 자료구조로 만들기
2. 나오는 값에 대해서 A, B 각각 경우의 수 개수를 구하기
3. 구한 개수를 이용해서 ret 값 만들기

 

 

1. 원형을 선형 자료구조로 만들기

해당 문제는 피자를 연속해서 팔기 때문에 피자가 원형이라 한바퀴 돌아서 피자를 선택해 판매를 할 수 있다.

 

즉, 7 2 2 2 1과 같은 피자가 있을 때 값 1 7 2 처럼 선택할 수도 있다는 뜻이다. 이를 원형 그대로 하는건 어렵다. 그래서 배열을 끝에 하나 더 붙이는 방법을 이용한다. 피자를 판매할 때 피자의 조각 범위 내에서만 팔 수 있으니까 뒤에 배열을 하나 더 붙이기만 하면 원형처럼 이용이 가능하다.

 

1개
7 2 2 2 1 7 2 2 2 1
-
  -
    -
      -
        -

2개
7 2 2 2 1 7 2 2 2 1
- -
  - -
    - -
      - -
        - - 이 다음부턴 같은 경우의 수

3개
7 2 2 2 1 7 2 2 2 1
- - -
  - - -
    - - -
      - - -
        - - - 이 다음부턴 같은 경우의 수

4개
7 2 2 2 1 7 2 2 2 1
- - - -
  - - - -
    - - - -
      - - - -
        - - - - 이 다음부턴 같은 경우의 수

5개
7 2 2 2 1 7 2 2 2 1
- - - - -

 

이렇게 선형적으로 모든 경우의 수를 찾을 수 있다. 그리고 여기서 알 수 있는 사실이 인덱스가 0부터가 아닌 1부터 시작한다고 하면, 1개일땐 idx 5까지이고 2개 일땐 idx 6까지, 3일때는 idx 7, 4일때는 idx 8까지임을 알 수 있다. 이걸 좀 일반화하면 전체 크기 n에 대해 n + 뽑는 개수 r - 1이 된다.

 

즉, 경우의 수마다 개수를 구하기위해서 n + r - 1 (n: 조각 개수, r: 뽑는 개수)까지 반복해야함을 의미한다.

 

 

 

2. 나오는 값에 대해서 A, B 각각 경우의 수 개수를 구하기

여기서는 누적합 로직이 쓰인다.

 

위의 경우의 수를 각각 구할 때 사실 하나씩 뽑아서 할 수도 있지만 그러면 3중 for문으로 구성할 수 밖에 없다.

뽑는 갯수(1->5)
	뽑는 경우의 수 별 마지막 인덱스 (뽑는 개수 -> n + 뽑는 개수 - 1)
		실제로 뽑기 (뽑는 개수 -> 0)

 

그럼 최악의 경우 뽑는 개수가 1000, 인덱스는 1000 * 2(이 부분은 부정확하나 1000인 것은 확실), 실제로 뽑는 것도 1000

= 2000000000 약 20억이다.

 

하지만 실제로 뽑는 경우를 누적합으로 처리하면 1000 * 1000 * 2

= 2000000 약 200만으로 줄어들 수 있다.

 

누적합을 만들기 전에 배열을 끝에 붙여놓고, 그대로 1 ~ n*2까지 누적합을 구해놓으면 된다. 그럼 원형이라도 문제없이 누적합을 사용할 수 있다. 한 가지 예를 들어보면..

 

3개
7 9 11 13 14 21 23 25 27 28
- - -
= 11 (7 2 2)

7 9 11 13 14 21 23 25 27 28 위의 누적합에서 아래 누적합을 뺀다.
- - -  -
-
= 6 (2 2 2)

7 9 11 13 14 21 23 25 27 28
- - -  -  -
- -
= 5 (2 2 1)

7 9 11 13 14 21 23 25 27 28
- - -  -  -  -
- - -
= 10 (2 1 7)

7 9 11 13 14 21 23 25 27 28
- - -  -  -  -  -
- - -  -
= 10 (1 7 2) 이 다음부터는 같은 경우의 수이므로 stop

 

이렇게 잘 적용되는 모습을 알 수 있다. index를 1부터 시작하는 이유는 누적합이다보니 A[i] += A[i - 1]; 과 같은 로직을 사용하는데 0부터 시작하면 0을 따로 처리해줘야 하니까 차라리 1부터 시작하는 것이다.

 

지금까지 원형의 자료구조를 선형의 자료구조로 바꾸고 누적합을 구하는 것까지 했다. 이제 해당 경우의 수를 어떻게 저장하느냐 인데 이건 Map으로 저장하였다. 그럼 어떤 수에 대한 경우의 수 개수를 바로바로 갱신할 수 있으니 편리하다.

 

 

 

3. 구한 개수를 이용해 ret 값 만들기

이제 구한 개수를 이용해 ret 값을 만들면 된다.

 

손님이 사려고 하는 피자의 조각 합이 7이라면 0 ~ 7까지 반복하면서 mapA.get(i) * mapB.get(7 - i)로 반복하면서 ret 값을 갱신하면 된다. 만약, i = 3이면 A 피자에서 3을 만들 수 있는 경우의 수 개수와 B 피자에서 4를 만들 수 있는 경우의 수 개수를 곱하면 A, B 피자를 이용해서 총합 7을 만들 수 있다.

 

만약 B 피자에서 4를 만들 수 없으면 애초에 이 경우 피자를 7로 만들 수 없는 경우이므로 넘어가면 된다. 한 가지 주의할 점은 한 피자에서 바로 7을 만드는 경우인데 이러면 저 로직 상 mapA.get(7) * mapB.get(0)이 되어버리니까 만들 수 없는 값이 나온다. 그래서 마지막 값에 대한 처리를 따로 해줘야한다.

 

 

코드

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

    static int ret = 0;
    static int[] A;
    static int[] B;
    static int m, n;
    static int pizza;
    static Map<Integer, Integer> mpa = new HashMap<>();
    static Map<Integer, Integer> mpb = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        pizza = Integer.parseInt(br.readLine());

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

        A = new int[m * 2 + 1];
        B = new int[n * 2 + 1];

        for (int i = 1; i <= m; i++) A[i] = A[i+m] = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) B[i] = B[i+n] = Integer.parseInt(br.readLine());

        for (int i = 1; i <= m * 2; i++) A[i] += A[i - 1];
        for (int i = 1; i <= n * 2; i++) B[i] += B[i - 1];

        int sum;

        for (int interval = 1; interval <= m; interval++) {
            for (int start = interval; start <= m + interval - 1; start++) {
                sum = A[start] - A[start - interval];
                if (!mpa.containsKey(sum)) mpa.put(sum, 1);
                else mpa.put(sum, mpa.get(sum) + 1);
                if (interval == m) break;
            }
        }

        for (int interval = 1; interval <= n; interval++) {
            for (int start = interval; start <= n + interval - 1; start++) {
                sum = B[start] - B[start - interval];
                if (!mpb.containsKey(sum)) mpb.put(sum, 1);
                else mpb.put(sum, mpb.get(sum) + 1);
                if (interval == n) break;
            }
        }

        if (mpa.containsKey(pizza))
            ret = mpa.get(pizza);
        if (mpb.containsKey(pizza))
            ret += mpb.get(pizza);
        for (int i = 1; i < pizza; i++)
            if (mpa.containsKey(i) && mpb.containsKey(pizza - i))
                ret += (mpa.get(i) * mpb.get(pizza - i));

        System.out.println(ret);
    }
}