[백준 2961] 도영이가 만든 맛있는 음식(Java) 정리

비트마스킹과 조합 알고리즘을 사용한다.

 

1) 해당 재료로 만들 수 있는 조합의 신맛과 쓴맛을 모두 계산한다.

2) 후에 신맛과 쓴맛의 차이 값을 구해서 제일 작은 값을 구한다. 

 

for(int[] d : dp) {
    d[0] = 1; //신맛 (곱해야해서 1로 초기화)
    d[1] = 0; //쓴맛 (더해야해서 0으로 초기화) 
}

public static void dyCook(int[][] dp, int[] sour, int[] bitter, int visited, int N) {
    for(int i = 1; i < (1 << N); i++) { //1(2) 부터 1111...1(2)까지 
        for(int j = 0; j < N; j++) { //각 재료에 대해
            if((i & (1 << j)) != 0) { //i에 j가 들어가 있으면  
                dp[i][0] *= sour[j]; 
                dp[i][1] += bitter[j];
            }
        }
    }
}

 

[전체 코드]

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

public class Main {
	public static void dyCook(int[][] dp, int[] sour, int[] bitter, int visited, int N) {
		for(int i = 1; i < (1 << N); i++) {
			for(int j = 0; j < N; j++) {
				if((i & (1 << j)) != 0) {
					dp[i][0] *= sour[j];
					dp[i][1] += bitter[j];
				}
			}
		}
	}
	
    public static void main(String[] args) {
        int N;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        try
        {
            N = Integer.parseInt(br.readLine());
            int[] sour = new int[N];
            int[] bitter = new int[N];
            int[][] dp = new int[(1 << N)][2];
            
            for(int[] d : dp) {
    			d[0] = 1;
    			d[1] = 0;
    		}
            
            for(int i = 0; i < N; i++) {
            	st = new StringTokenizer(br.readLine());
            	sour[i] = Integer.parseInt(st.nextToken());
            	bitter[i] = Integer.parseInt(st.nextToken());
            }
            
            dyCook(dp, sour, bitter, 0, N);
            
            int min = 1000000000;
            int cookedVal = 0;
            
            for(int i = 1; i < (1 << N); i++) {
            	cookedVal = Math.abs(dp[i][0] - dp[i][1]);
            	if(cookedVal < min) min = cookedVal;
            }
            
            bw.write(Integer.toString(min));
            bw.flush();
            bw.close();
            br.close();
        }catch (Exception e)
        {
            e.printStackTrace();
        }
    }
}