백준 2961번: 도영이가 만든 맛있는 음식 [백트래킹][비트마스크][브루트포스] -Java

https://www.acmicpc.net/problem/2961

2961번: 도영이가 만든 맛있는 음식

 

백트래킹 + 비트마스킹을 이용하여 푼 문제

재료의 조합을 비트마스크에 저장하였다

 

Ex. { 1 , 2, 3, 4, 5} ==> 11111(2)

{1,4,5} ==> 11001(2)

 

가장 오른쪽부터 idx = 0 이라고 보면 된다.

 

 

<Java 코드>

 

디버깅 하기 귀찮아서 Syso()를 많이 찍었다ㅋ

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

public class Main {

	public static boolean visit[];
	public static int N, res = Integer.MAX_VALUE;
	public static Food arr[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new Food[N];
		visit = new boolean[1050];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = new Food(Integer.parseInt(st.nextToken())
					,Integer.parseInt(st.nextToken()));
		}
		
		fun(0,0);
		
		System.out.println(res);

	}
	
	public static void fun(int idx, int mask) {
//		System.out.println(str);
		for (int i = idx; i < N; i++) {
			
			int newMask = 1 << i;
			if(visit[mask|newMask]) //조합으로 들른적 있는가?
				continue;
			
			visit[mask|newMask] = true;
			
			//답 계산하기
			res= Math.min(res, makeResult(mask|newMask));
			
			fun(i+1, mask|newMask);

		}
	}
	
	public static int makeResult(int mask) {
		
		String bin = Integer.toBinaryString(mask); //10진수 -> 2진수 출력
//		System.out.println("bin : "+ bin);
		int sumBitter = 0;
		int sumSour = 1;
		
		for (int i = 0; i < bin.length(); i++) {
//			System.out.println("charAt: " + bin.charAt(bin.length()-1-i));
			if(bin.charAt(bin.length()-1-i)=='1') {
				sumBitter+= arr[i].bitter;
				sumSour*= arr[i].sour;
			}
		}
		
//		System.out.println("sumBitter: "+sumBitter+", sumSour: "+sumSour);
		return Math.abs(sumBitter-sumSour);
	}

}

class Food {
	int bitter;
	int sour;
	
	public Food(int s, int b) {
		this.bitter = b;
		this.sour = s;
	}
}