백준 2632번: 피자판매 (Java)

접근

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

피자를 판매할 때 연속하는 피자의 조각들로 판매할 수 있습니다. 따라서 m 조각으로 나뉜 피자 A가 1번 조각부터 m번 조각까지 있다고 했을 때 다음과 같이 경우의 수를 확인할 수 있습니다.

1, 1~2, 1~3, 1~4, ... , 1~(m-1), 1~m,

2, 2~3, 2~4, 2~5, ... , 2~m, 2~1

3, 3~4, 3~5, 3~6, ... , 3~1, 3~2

...

m, m~1, m~2, m~3, ... , m~(m-2), m~(m-1)

총 m*m 경우의 수로 보이지만, 1~m, 2~1, 3~2, ... , m~(m-1) 은 모두 피자 전체를 나타내는 조각을 의미하여 중복이고, 추가적으로 피자를 선택하지 않는 0이 더해집니다.

이 과정에서 구매자가 사고 싶어하는 크기의 조각보다 큰 경우는 계산할 필요 없으므로, 위의 조각들을 탐색, 순환하는 과정에서 구매 희망 숫자보다 큰 경우를 제외해줍니다.

같은 과정을 두 피자 모두에게 진행해주면, A 피자를 선택할 수 있는 경우의 수와, B 피자를 선택할 수 있는 경우의 수를 모두 구할 수 있습니다.

이후, 투포인터 방식을 이용하여 A 피자와 B 피자를 선택하는 방식으로 정답을 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static int T, res;
  static int m, n;
  static int[] A, B;
  static boolean[] check;
  static ArrayList<Integer> AList = new ArrayList<>();
  static ArrayList<Integer> BList = new ArrayList<>();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    T = Integer.parseInt(br.readLine());
    String[] mn = br.readLine().split(" ");
    m = Integer.parseInt(mn[0]);
    n = Integer.parseInt(mn[1]);
    A = new int[m];
    B = new int[n];
    for (int i = 0; i < m; i++) {
      A[i] = Integer.parseInt(br.readLine());
    }
    for (int i = 0; i < n; i++) {
      B[i] = Integer.parseInt(br.readLine());
    }
    br.close();
    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() && 0 <= rightIdx) {
      int lv = AList.get(leftIdx);
      int rv = BList.get(rightIdx);
      if (lv + rv == T) {
        int lc = 0, rc = 0;
        while (leftIdx < AList.size() && AList.get(leftIdx) == lv) {
          lc++;
          leftIdx++;
        }
        while (0 <= rightIdx && BList.get(rightIdx) == rv) {
          rc++;
          rightIdx--;
        }
        res += lc * rc;
      }
      if (lv + rv > T) rightIdx--;
      if (lv + rv < T) leftIdx++;
    }
    System.out.println(res);
  }

  static void getSum(int sum, int sIdx, int eIdx, boolean[] check, int[] arr, List<Integer> list) {
    if (eIdx == arr.length) eIdx = 0;
    list.add(sum);

    if (check[eIdx] == false && sum <= T && eIdx != sIdx - 1) {
      check[eIdx] = true;
      getSum(sum + arr[eIdx], sIdx, eIdx + 1, check, arr, list);
    }
    return;
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!