백준 - 2961번 도영이가 만든 맛있는 음식

풀이-1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2961 {
    
	static int N;//재료 수
	static Food [] foods;
	static int minGap = Integer.MAX_VALUE; //음식 맛의 최소 차이(정답)
	static boolean[] selected; //부분집합의 선택/비선택 표현
		
	static class Food{
	   //서로 관련된 속성을 표현
	   //1.속성
	   //2.(속성을 초기화해주는)생성자
	   //3. 옵션 toString()오버라이딩 : 객체가 갖는 속성을 편히 보기 위해서 (디버깅 용도)
		int sour;//신맛
		int bitter;//쓴맛
		
		public Food(int sour, int bitter) {
			this.sour = sour;
			this.bitter = bitter;
		}
	}
	
	public static void main(String[] args) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine()); //재료개수  "1"
      foods = new Food[N];
      selected = new boolean[N];
      
//      하나의 재료
//      Integer.parseInt(tokens.nextToken()); //신맛
//      Integer.parseInt(tokens.nextToken()); //쓴맛
      for(int i=0; i<N; i++) { //foods 배열
    	  StringTokenizer tokens = new StringTokenizer(br.readLine()); //신맛 쓴맛 "3 10"
    	  
    	  //(신맛,쓴맛을 표현하는)하나의 재료를 담기 위해 Food객체 사용
    	  //재료가 여러개 있으므로 foods[]배열 사용
    	 foods[i] = new Food(Integer.parseInt(tokens.nextToken()), 
    			          Integer.parseInt(tokens.nextToken()));
    	  
      }
      //입력 끝
      
      subset(0);//부분집합 구하기
      
      System.out.println(minGap);
      
      br.close();
	}

	private static void subset(int depth) {
        if(depth == N) {//재료가 전부 (사용/비사용)선택되었다면
        	
        	//누적을 위한 변수 선언
        	int sour=1;  //신맛 (곱)
        	int bitter=0;//쓴맛 (합)
        	
        	for(int i=0; i<N; i++) {//전체 재료 인덱스
        		
        		//각 재료가 선택되었다면
        		if(selected[i]) {
        			//신맛은 곱하여 누적, 쓴맛은 더하여 누적
        			//foods[i] == Food 객체
        			sour  *= foods[i].sour;
        			bitter += foods[i].bitter;
        		}
        		
        	}//==> 선택된 각 재료에 대한 누적이 끝났다면
        	
        	if(sour == 1 && bitter==0) { //선택된 재료가 하나도 없다면!!!!  ==> 공집합 이라면!!!
        		return;
        	}
        	
        	
        	
          if(minGap > Math.abs(sour - bitter)) { //이전 재료의 차이와 비교
        	minGap = Math.abs(sour - bitter); //새로운 재료의 차이가 적을때 값을 갱신
          }
        	
        	return;
        }
		
		//depth번지에 해당하는 요소를 선택하지 않고 재귀호출
		selected[depth] = false;
		subset(depth+1); //(현재 재료를 비사용후)다음 재료 알아보기
		
		//depth번지에 해당하는 요소를 선택하고 재귀호출
		selected[depth] = true; 
		subset(depth+1); //(현재 재료를 사용후)다음 재료 알아보기
		
	}
	
	

}

 

풀이-2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2961_v2 {
    
	static int N;//재료 수
	static Food [] foods;
	static int minGap = Integer.MAX_VALUE; //음식 맛의 최소 차이(정답)
		
	static class Food{
	   //서로 관련된 속성을 표현
	   //1.속성
	   //2.(속성을 초기화해주는)생성자
	   //3. 옵션 toString()오버라이딩 : 객체가 갖는 속성을 편히 보기 위해서 (디버깅 용도)
		int sour;//신맛
		int bitter;//쓴맛
		
		public Food(int sour, int bitter) {
			this.sour = sour;
			this.bitter = bitter;
		}
	}
	
	public static void main(String[] args) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine()); //재료개수  "1"
      foods = new Food[N];
      
//      하나의 재료
//      Integer.parseInt(tokens.nextToken()); //신맛
//      Integer.parseInt(tokens.nextToken()); //쓴맛
      for(int i=0; i<N; i++) { //foods 배열
    	  StringTokenizer tokens = new StringTokenizer(br.readLine()); //신맛 쓴맛 "3 10"
    	  
    	  //(신맛,쓴맛을 표현하는)하나의 재료를 담기 위해 Food객체 사용
    	  //재료가 여러개 있으므로 foods[]배열 사용
    	 foods[i] = new Food(Integer.parseInt(tokens.nextToken()), 
    			          Integer.parseInt(tokens.nextToken()));
    	  
      }
      //입력 끝
      
      subset(0, 1,0);//부분집합 구하기
      
      System.out.println(minGap);
      
      br.close();
	}

	private static void subset(int depth,int sour,int bitter  ) {
        if(depth == N) {//재료가 전부 (사용/비사용)선택되었다면
        	
    	  if(sour == 1 && bitter==0) { //선택된 재료가 하나도 없다면!!!!  ==> 공집합 이라면!!!
    		return;
    	  }
          if(minGap > Math.abs(sour - bitter)) { //이전 재료의 차이와 비교
        	minGap = Math.abs(sour - bitter); //새로운 재료의 차이가 적을때 값을 갱신
          }        	
        	return;
        }		

		//재료를 선택하지 않았을때
		subset(depth+1, sour,                     bitter);
		
		//재료를 선택했을때
		subset(depth+1, sour*foods[depth].sour,   bitter+foods[depth].bitter);		
	}
	
	

}