문제

https://www.acmicpc.net/problem/2961
도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력
첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력
첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

예제 입력 1
1
3 10
예제 출력 1
7

예제 입력 2
2
3 8
5 8
예제 출력 2
1

예제 입력 3
4
1 7
2 6
3 8
4 9
예제 출력 3
1
2, 3, 4번 재료를 사용한다면, 요리의 신맛은 2×3×4=24, 쓴맛은 6+8+9=23이 된다. 차이는 1이다.

접근

이 문제는 코테 준비를 이제 막 시작했을 때쯤 한 번 풀었던 문제이다. 당시 작성한 글..
이번에 코테 스터디원 중에 한 분이 비트 마스킹을 이해해보고 싶다고 하시면서 이 문제를 가져오셔서 다시 풀어보게 되었다.

당시 비트 마스킹을 처음 접하고 이해하려고 골머리를 앓았어서 시간이 꽤 지났는데도 문제가 익숙했다.
재료의 개수인 N이 최대 10으로 매우 작기 때문에 그냥 완전 탐색을 하면 풀리는 문제이다.
어떤 재료를 선택하는 경우, 선택하지 않는 경우 각각을 재귀적으로 탐색한 후 탐색이 끝나면 이전 상태로 돌려 놓는 백트래킹 식으로 풀면 된다.
재료를 선택했다면 해당 비트를 1로 마킹하면 되고.

구현

import java.io.*;

class Main {
    static int[][] taste;
    static int minGap = 1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        taste = new int[N][2];
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            taste[i][0] = Integer.parseInt(input[0]);
            taste[i][1] = Integer.parseInt(input[1]);
        }        
        backtracking(0, 0, 1, 0);
        System.out.println(minGap);
    }

    private static void backtracking(int selection, int depth, int sourness, int bitterness) {
        if (depth == taste.length && selection > 0) {
            minGap = Math.min(minGap, Math.abs(sourness - bitterness));
        }
        for (int i = depth; i < taste.length; i++) {
            // i번째 재료를 선택
            selection |= (1 << i);
            backtracking(selection, i + 1, sourness * taste[i][0], bitterness + taste[i][1]);
            // i번째 재료를 선택하지 않음
            selection &= ~(1 << i);
            backtracking(selection, i + 1, sourness, bitterness);
        }
    }
}

예전에 풀었을 때 모범 답안이라고 내가 가져왔던 코드보다 이번에 다시 푼 코드가 더 빠르네ㅋㅋ...