[BOJ] 2632 피자판매 Java 풀이

 

 

BOJ 2632번 피자판매

 

문제의 첫 인상이 범상치 않다. 그림이 등장하는데, 원이 나올 때부터 긴장된다. 

하지만, 읽어보면 문제 지문 자체는 크게 복잡할 게 없다.

이전에 연습해오던 부분합, 투 포인터 문제와 유사한 것 같은데 먼저 원형으로 구성되어 있다는 점이 낯설다.
어떻게 구현해야하는지 끙끙대다가, 결국은 다른 분의 풀이를 참고해 해결했다.
참고: https://kohen.tistory.com/20

순환 큐라는 개념이 있다고 한다. 
아직 본격적으로 찾아 공부해보지 않았으나, 이번 문제에서 이 유형에 익숙해지고자 했다.

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

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

private static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, List list) {
	// 들어온 인덱스가 끝이면 원형이기 때문에 다시 0으로 처리
	if(idx == arr.length) idx = 0;
	
	list.add(sum);
	
	// 아직 안 담은 피자조각에 대해서만 판매함 && 마지막 인덱스 값을 계속 저장하지 않음 && 순열의 합이 이미 타겟을 넘어서면 계산하지 않음
	if(check[idx] == false && idx != startIdx -1 && sum <= S) {
		check[idx] = true;
		getSum(sum +arr[idx], startIdx, idx +1, check, arr, list);
	}else {
		return;
	}
}

 

다른 문제와 투 포인터를 사용하는 부분은 유사한데, 원형으로 존재하는 2개 피자판의 부분 합을 어떻게 담아주는지가 이 문제의 핵심이었다. 

원형 피자판을 쭉 펴서 하나의 배열로 볼 수 있다. 첫 조각은 어디서든 시작할 수 있기 때문에 반복문을 통해 모든 인덱스에서 시작하는 경우를 모두 리스트에 담아준다. 계속해서 한 조각씩 담아주는데, 구조상 배열로 표현했지만 원형이기 때문에 피자판의 마지막 인덱스를 넘어가면 다시 0으로 바꿔준다. 담기 시작한 조각에서부터 원형을 돌아 마지막 조각까지 오면 특이하게 마지막 조각은 담지 않고 return한다. 이는 현재 피자판의 부분합을 구해주는 작업이기에 마지막 조각까지 더해서 담아버리는 경우는 피자 한 판을 모두 선택한 경우인데, 반복문을 통해 첫 조각 인덱스가 바뀔때마다 중복해서 들어간다. 따라서 if문 내의 'idx != startIdx -1' 구문을 통해 첫 조각을 0번 인덱스에서 시작할 때 때에만 피자판 모든 조각을 선택하는 경우로 list에 추가하도록 한다.

package exhaustiveSearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class P2632 {
	static int M, N, S;
	static int[] A, B;
	static int ans;
	static boolean check[];
	static ArrayList<Integer> AList = new ArrayList<>();
	static ArrayList<Integer> BList = new ArrayList<>();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		S = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		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());
		}

		for(int i = 0; i < M; i++) {
			// check배열 초기화
			check = new boolean[M];
			// 첫 번째 조각 담기  
			check[i] = true;
			getSum(A[i], i, i+1, check, A, AList);
			
		}
		
		for(int i = 0; i < N; i++) {
			// check배열 초기화
			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);
		
		getAns();
		
		System.out.println(ans);
		
	
		
		
	} // end of main
	

	// 부분합 구하기
	// 순환 큐 구현하듯이
	private static void getSum(int sum, int startIdx, int idx, boolean[] check, int[] arr, List list) {
		// 들어온 인덱스가 끝이면 원형이기 때문에 다시 0으로 처리
		if(idx == arr.length) idx = 0;
		
		list.add(sum);
		
		// 아직 안 담은 피자조각에 대해서만 판매함 && 마지막 인덱스 값을 계속 저장하지 않음 && 순열의 합이 이미 타겟을 넘어서면 계산하지 않음
		if(check[idx] == false && idx != startIdx -1 && sum <= S) {
			check[idx] = true;
			getSum(sum +arr[idx], startIdx, idx +1, check, arr, list);
		}else {
			return;
		}
	}
	
	// 투 포인터로 부분합들을 하나는 작은 수부터, 하나는 큰 수부터 더해보며 목표 수와 비교하며 ans 계산하기
	private static void getAns() {
		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 == S) {
				int lc = 0;
				while(leftIdx < AList.size() && AList.get(leftIdx) == lv) {
					lc++;
					leftIdx++;
				}
				
				int rc = 0;
				while(rightIdx >= 0 && BList.get(rightIdx) == rv) {
					rc++;
					rightIdx++;
				}
				
				ans += lc * rc;
			}else if(lv + rv < S) {
				// 두 부분합의 합이 원하는 합보다 작은 경우
				leftIdx++;
			}else {
				// 두 부분합의 합이 원하는 합보다 큰 경우
				rightIdx--;
			}
		}
	}
}