백준 - 도영이 음식(2961) / 비트마스킹 + 조합

오늘 풀어본 문제는 ⭐도영이가 만든 맛있는 음식 이라는 문제다.

1. 문제 요약

• 각 재료마다 쓴 맛과 신 맛이 주어진다.
• 주어진 재료들을 적당히 섞어 쓴 맛과 신 맛의 차이를 최소로 줄이고자 한다.
  • 신 맛은 사용된 재료들의 총곱 / 쓴 맛은 사용된 재료들의 총합
• 재료는 1개 이상 무조건 사용한다.

2. 입출력

[입력]

• 재료의 개수 N(1 ≤ N ≤ 10)
• 1,000,000,000보다 작은 양의 정수

[출력]

• 신맛과 쓴맛의 가장 최소 차이를 출력하라.

3. 알고리즘

• 조합 문제
• 자료의 개수가 10개. boolean 대신 비트마스킹을 써서 표시해보기
• Long형 써야 함

4. 코드

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

public class Main {
    static int N;
    static int [][] TASTE;
    static long ANSWER;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        TASTE = new int[N][2];
        
        for(int i=0; i<N; i++){
            TASTE[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(s -> Integer.parseInt(s))
                    .toArray();
        }

        ANSWER = Long.MAX_VALUE;
        johap(0, 0, 1, 0);

        System.out.println(ANSWER);
    }

    static void johap (int start, int visit, long sour, long bitter) {
        if(start == N)
            return;

        for(int i = start; i<N; i++){
            if ((visit & (1 << i)) != 0) continue;
            visit |= (1<<i);
            long ns = sour * TASTE[i][0];
            long nb = bitter + TASTE[i][1];
            long newTaste = Math.abs(ns - nb);
            ANSWER = Math.min(ANSWER, newTaste);
            johap(i + 1, visit, sour * TASTE[i][0], bitter + TASTE[i][1]);
            visit &= ~(1<<i);
        }
    }
}

5. 알게된 점

사실 비트마스킹을 연습해보고자 푼 문제다.

비트마스킹으로 현재 방문했는지 확인하는 조건문

if ((visit & (1 << i)) != 0) {
	continue;
}

비트마스킹으로 i번째 방문체크

 visit |= (1<<i);

visit의 초기값은 0에서 시작한다.

비트마스킹으로 i번째 방문해제

visit &= ~(1<<i);