백준 2632 (피자판매)

문제

---

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

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

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

 

 

 

 

 

풀이

---

이 문제가 이분탐색이 맞는지는 아직도 잘 모르겠지만..

문제의 푸는 기본 풀이방식은

• A, B의 조각들 합의 부분집합을 각각 모두 구한다.
• A, B의 조각들 합의 부분집합을 오름차순으로 정렬한다.
• A는 제일작은 합부터 B는 제일 큰 합부터 조각개수가 맞는지 확인한다. (B와 A의 훑는 순서는 변해도 상관없다.)

이 알고리즘을 통해 풀게 될것이다.

 

문제를 풀때의 주의사항

1. 피자는 연속된 조각만 선택가능
2. 피자는 원이므로 처음에 주어진 조각과 마지막에 주어진 조각은 이어져있다.

이 두가지의 주의사항을 잘 생각하면서 문제를 풀면된다.

 

static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, List<Integer> list) {
		
	if(idx == arr.length) {
		idx = 0;
	}
	
	list.add(sum);
	
	if(check[idx] == false && idx != startIdx - 1 && sum <= want ) {
		check[idx] = true;
		getSum(sum + arr[idx] , startIdx, idx + 1, check, arr, list);
	
	}
}

우선 각각 피자들의 조각들 합의 부분집합을 구하는 코드다.

 

check[idx] == false는 현재의 부분집합의 시작점을 체크하기 위한 코드다.

 

idx != startIdx - 1의 조건은 원의 특성상 1번조각부터 5번조각을 선택하던 2번조각부터 1번조각까지 선택하던 모두를 선택한 경우다(2번 주의 사항, 1번주의 사항)

위 경우를 해결하기 위해 idx = 0 인경우를 제외하고는 마지막의 하나전 조각은 포함하지 않게 하기 위한 조건이다

 

문제에서 주어진 예시에서 A피자를 예를들면,

2, 2, 1, 7, 2 -> idx = 0 일때 선택

2, 1, 7, 2 -> idx = 1 일때 idx != startIdx -1 조건에 의해 idx = 0 의 조각은 선택되지 않는다.

1, 7, 2, 2 -> idx = 2 일때 idx != startIdx -1 조건에 의해 idx = 1 의 조각은 선택되지 않는다.

 

---

이렇게 차례차례 선택된다고 보면 된다.

 

sum <= want  이조건은 현재까지의 합이 선택하고자하는 조각개수보다 작으면 더 넣어주고 아니면 그만두는 조건이다. 원하는 조각개수보다 더큰 조각은 선택할 필요가 없기 때문이다.

 

if(idx == arr.length) {
	idx = 0;
}

위 조건을 통해서 피자는 원이므로 마지막 인덱스일경우 0으로 바꿔주었다. (2번 주의사항)

 

 

이렇게 구해진 조각 합을 통해 A피자와 B피자의 조합을 구한다.

int left = 0, right = BList.size() -1;
int answer = 0;
while(left < AList.size() && right >= 0) {
	int leftSum = AList.get(left);
	int rightSum = BList.get(right);
			
	if(leftSum + rightSum == want) {
		int leftCount = 0;
		int rightCount = 0;
				
		while(left < AList.size() && AList.get(left) == leftSum) {
			leftCount++;
			left++;
		}
		
		while(right >= 0  && BList.get(right) == rightSum) {
			rightCount++;
			right--;
		}
		
		answer += leftCount * rightCount;
	}			
	else if(leftSum + rightSum > want) {
		right--;
	}
	else {
		left++;
	}
}

위 코드를 통해 조합을 만드는데,

 

while(left < AList.size() && AList.get(left) == leftSum) {
	leftCount++;
	left++;
}
				
while(right >= 0  && BList.get(right) == rightSum) {
	rightCount++;
	right--;
}

위 두 while 문은 조각의 특성상 크기가 같은 조각이 여러개있으면 같은 크기의 크기합이 생길 수 밖에 없다.

같은 크기합의 조각들을 찾아 개수를 세주어야한다.

 

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	static int want;
	static int a, b;
	static int[] A, B;
	static boolean[] check;
	static List<Integer> AList, BList;
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		want = Integer.parseInt(bufferedReader.readLine());
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		
		A = new int[a];
		B = new int[b];
		
		AList = new ArrayList<Integer>();
		BList = new ArrayList<Integer>();
		
		for(int i = 0 ; i < a ; i++) {
			A[i] = Integer.parseInt(bufferedReader.readLine());
		}
		for(int i = 0 ; i < b ; i++) {
			B[i] = Integer.parseInt(bufferedReader.readLine());
		}
		
		for(int i = 0 ; i < a ; i++) {
			check = new boolean[a];
			check[i] = true;
			getSum(A[i], i, i+1, check, A, AList);
		}
		
		for(int i = 0 ; i < b ; i++) {
			check = new boolean[b];
			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 left = 0, right = BList.size() -1;
		int answer = 0;
		while(left < AList.size() && right >= 0) {
			int leftSum = AList.get(left);
			int rightSum = BList.get(right);
			
			if(leftSum + rightSum == want) {
				int leftCount = 0;
				int rightCount = 0;
				
				while(left < AList.size() && AList.get(left) == leftSum) {
					leftCount++;
					left++;
				}
				
				while(right >= 0  && BList.get(right) == rightSum) {
					rightCount++;
					right--;
				}
				
				answer += leftCount * rightCount;
			}			
			else if(leftSum + rightSum > want) {
				right--;
			}
			else {
				left++;
			}
		}
		
		System.out.println(answer);
	}
	
	static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, List<Integer> list) {
		
		if(idx == arr.length) {
			idx = 0;
		}
		
		list.add(sum);
		
		if(check[idx] == false && idx != startIdx - 1 && sum <= want ) {
			check[idx] = true;
			getSum(sum + arr[idx] , startIdx, idx + 1, check, arr, list);
		}
		
	}
}