[백준 알고리즘 - 2632] 피자판매 - java/완전탐색(재귀호출)

진짜 전혀 어려울 것 없는 문제였는데, 조건문 계속 삽질하고 예외케이스 하나 계속 못찾아서 4시간 걸렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 발전좀하자!! 제발!

A, B에 대한 부분집합을 각각 구해준 뒤 하나씩 합해서 경우의 수를 세면 되는 문제인데,

첫 번째 신경써야 할 부분은 

1. "연속된" 원소만 더해야 할 것 

-> 따라서 최대 1000000개이기 때문에 완전탐색이 가능하다

-> 난 여기에 추가로 S가 넘지 않으면 아예 탐색을 종료하도록 구현하였다. 아주 조금이라도 시간을 줄이겠다는 욕망 ,,? 

2. 둘 중 하나는 아예 담지 않아도 되게 할 것

-> 0을 추가해준 뒤 오름차순 정렬해주면 쉽게 처리 가능하다.

3. 배열에 담았을 시 맨 뒤를 담으면 끝나는 것이 아닌 맨 앞원소를 다시 담아도 연속한 경우라는거!

-> boolean 타입의 check 배열을 통해 상태를 저장했고, 담을 원소의 index가 길이와 일치할 때 0으로 변경해줌으로써 처리해주었다.

그리고 대망의 내가 삽질했던 구간 ,, ^^ .. 넘 힘들었다 하하

4. 피자 한 판 전체를 담을 수 있는 경우의 수는 각각 1가지만 이라는거 !!!

-> 3번을 처리해주고나니 전체를 담는 경우의 수가 원소의 수만큼 추가되었다. 그러니 당연히 틀릴 수밖에 ㅠㅠ

코드는 다음과 같다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;



class Main{
	/*
	 * sum: 현재까지 면적의 합 
	 * idx: 현재 포함할 피자
	 * newArr: 연속된 집합의 합을 저장하는 arrayList
	 * start_idx: 시작인덱스 -(start_idx부터 피자를 담기 시작)
	 * check: 담았는지 상태 저장/ true이면 한바퀴 돌았다고 판단 
	 * S: 고객이 원하는 피자. sum이 이 이상이면 끝냄  
	 */
	public static void makePizza(long S, ArrayList<Long> newArr, long[] arr, int start_idx, boolean[] check, int idx, long sum) {

		if(idx==arr.length)//끝까지 담았고 첫번째 조각으로 넘어감 
			idx=0;

		newArr.add(sum);
		if(check[idx]==false && sum + arr[idx] <= S && idx != start_idx-1) {
			check[idx]=true;
			makePizza(S, newArr, arr, start_idx, check, idx+1, sum+=arr[idx]);
		}else 
			return;

	}
	
       public static void main(String[] args) throws IOException {
          
          BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
          Long S=Long.parseLong(br.readLine());
          
          StringTokenizer stringTokenizer=new StringTokenizer(br.readLine());
          
          int m=Integer.parseInt(stringTokenizer.nextToken());
          int n=Integer.parseInt(stringTokenizer.nextToken());
          
          long[] A=new long[m];
          long[] B=new long[n];
          
          for(int i=0; i<m; i++)
        	  A[i]=Long.parseLong(br.readLine());
          
          for(int i=0; i<n; i++)
        	  B[i]=Long.parseLong(br.readLine());
          
          ArrayList<Long> new_A=new ArrayList<>();
          ArrayList<Long> new_B=new ArrayList<>();
          
          
          
          boolean[] check;
          for(int i=0; i<m; i++) {
        	  check=new boolean[m];
        	  check[i]=true;//첫번째 조각 담음 
        	  makePizza(S, new_A,A,i, check, i+1, A[i]);
          }

          for(int i=0; i<n; i++) {
        	  check=new boolean[n];
        	  check[i]=true;
        	  makePizza(S, new_B,B,i, check, i+1, B[i]);
          }
          
          new_A.add(new Long(0));//아예 담지 않는 경우
          new_B.add(new Long(0));
        
          
         Collections.sort(new_A);
          Collections.sort(new_B);

          long count=0;
          int left=0;
          int right=new_B.size()-1;
          while(left < new_A.size() && right >=0) {
              long ls=new_A.get(left);
              long rs=new_B.get(right);
               
              if(ls+rs == S) {//S와 일치하면,  각 분할 집합에서 해당 합을 지니는 원소의 개수를 셈
                long lc=0; 
                while(  left<new_A.size() && new_A.get(left)== ls) {
                  lc++;
                  left++;
                }
                 
                long rc=0;
                while( right >=0 && new_B.get(right)== rs) {
                  rc++;
                  right--;
                }
                   
                count+=lc*rc;         
              }
               
              if(ls+rs > S)
                right--;
              if(ls+rs < S)
                left++;
               
            }
          
          
          
          System.out.println(count);
          
     }


       
}