[백준] 2632 피자 판매

---

피자는 A 종류 이거나 B 종류이거나 A와 B 혼합하여 판매할 수 있다. 그리고 한 종류의 피자 조각 을 2개 이상 판매할 때 그 조각들은 반드시 연속해야한다.

 

'조각들이 연속해야한다'는 부분에서 A와 B 각각 누적합을 구해야함을 알 수 있다. 그리고 구해진 누적합을 이분탐색을 통해 고객이 원하는 피자의 크기를 구할 수 있다.

 

누적합 구하기

피자는 원형이기 때문에 순환 배열(Circular Array) 누적합을 구해야한다. start(front), end(rear) 포인터를 사용해야한다.

start와 end 포인터를 한 칸씩 이동하면서 누적합을 구한다. 단 start 포인터가 다시 0이 되면 종료한다. 

 

start에서 end까지 모든 수의 누적합이 구매자가 원하는 크기 보다 작거나 같을 경우 조각의 개수 만큼 중복된다.

따라서 start ~ end-1까지 누적합을 구하고 마지막에 start ~ end까지 누적합이 구매자가 원하는 크기 보다 작을 경우 누적합 배열에 포함 시킨다.

 

이분 탐색

left, right 투 포인터를 사용한다. left는 A 피자의 첫 번째 누적합 원소를 가리키는 포인터이다. right는 B 피자의 마지막 누적합 원소를 가리키는 포인터이다. 

 

Python

 

	from sys import stdin
	from collections import defaultdict
	readline = stdin.readline
	T = int(readline())
	N, M = map(int, readline().split())
	A = [int(readline()) for _ in range(N)]
	B = [int(readline()) for _ in range(M)]
	def solve():
	stack_sum_A = list(sorted(get_stack_sum(A)))
	stack_sum_B = list(sorted(get_stack_sum(B)))
	A_count = get_count_as_dict(stack_sum_A)
	B_count = get_count_as_dict(stack_sum_B)
	res = binary_search(A_count, B_count)
	print(res)
	def get_count_as_dict(arr):
	count = defaultdict(int)
	for a in arr:
	if a not in count.keys():
	count[a] = 0
	count[a] += 1
	return count
	def binary_search(dict1, dict2):
	arr1 = list(sorted(list(dict1.keys())))
	arr2 = list(sorted(list(dict2.keys())))
	left, right = 0, len(arr2) - 1
	res = dict1[T] + dict2[T]
	while left < len(arr1) and right >= 0:
	cur = arr1[left] + arr2[right]
	if cur > T:
	right -= 1
	elif cur < T:
	left += 1
	else:
	res += (dict1[arr1[left]] * dict2[arr2[right]])
	left += 1
	right -= 1
	return res
	# 누적합
	# Circular
	def get_stack_sum(arr):
	res = []
	start = 0
	end = len(arr) - 1
	# 순환 배열 누적합
	while True:
	_sum = 0
	i = start
	while i != end:
	_sum += arr[i]
	if _sum > T: break
	res.append(_sum)
	i = (i + len(arr) + 1) % len(arr)
	start = (start + len(arr) + 1) % len(arr)
	end = (start + len(arr) - 1) % len(arr)
	# 시작점이 다시 처음으로 돌아오면 종료
	if start == 0: break
	_sum = sum(arr)
	if _sum <= T:
	res.append(_sum)
	return res
	solve()

view raw BOJ2632.py hosted with ❤ by GitHub

Java

 

	import java.util.*;
	import java.io.*;
	public class BOJ2632 {
	static int T, N, M;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	T = Integer.parseInt(br.readLine());
	StringTokenizer st = new StringTokenizer(br.readLine());
	N = Integer.parseInt(st.nextToken());
	M = Integer.parseInt(st.nextToken());
	int[] A = new int[N];
	int[] B = new int[M];
	for(int i=0;i<N;i++){
	A[i] = Integer.parseInt(br.readLine());
	}
	for(int i=0;i<M;i++){
	B[i] = Integer.parseInt(br.readLine());
	}
	int[] stackSumA = getStackSum(A);
	int[] stackSumB = getStackSum(B);
	Map<Integer, Integer> ACount = getCountAsMap(stackSumA);
	Map<Integer, Integer> BCount = getCountAsMap(stackSumB);
	binarySearch(ACount, BCount);
	}
	public static int[] getStackSum(int[] arr){
	ArrayList<Integer> res = new ArrayList<>();
	int start = 0;
	int end = arr.length - 1;
	while(true){
	int i = start;
	int sum = 0;
	while(i != end){
	sum += arr[i];
	if(sum > T) break;
	res.add(sum);
	i = (i + arr.length + 1) % arr.length;
	}
	start = (start + arr.length + 1) % arr.length;
	end = (start + arr.length - 1) % arr.length;
	if(start == 0) break;
	}
	int sum = 0;
	for(int i=0;i<arr.length;i++){
	sum += arr[i];
	}
	if(sum <= T){
	res.add(sum);
	}
	int[] returnValue = new int[res.size()];
	for(int i=0;i<res.size();i++){
	returnValue[i] = res.get(i);
	}
	return returnValue;
	}
	public static void binarySearch(Map<Integer, Integer> ACount, Map<Integer, Integer> BCount){
	ArrayList<Integer> arr1 = new ArrayList<>(ACount.keySet());
	ArrayList<Integer> arr2 = new ArrayList<>(BCount.keySet());
	Collections.sort(arr1);
	Collections.sort(arr2);
	int left = 0, right = arr2.size() - 1;
	int res = ACount.getOrDefault(T, 0) + BCount.getOrDefault(T, 0);
	while(left < arr1.size() && right >= 0){
	int cur = arr1.get(left) + arr2.get(right);
	if(cur > T){
	right--;
	} else if(cur < T){
	left++;
	} else {
	res += (ACount.get(arr1.get(left)) * BCount.get(arr2.get(right)));
	left++;
	right--;
	}
	}
	System.out.println(res);
	}
	public static Map<Integer, Integer> getCountAsMap(int[] arr){
	Map<Integer, Integer> count = new HashMap<>();
	for(int num : arr){
	count.put(num, count.getOrDefault(num, 0) + 1);
	}
	return count;
	}
	}

view raw BOJ2632.java hosted with ❤ by GitHub