백준 2961 도영이가 만든 맛있는 음식 java (brute force, bit masking)

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

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

 

 

 

요즘따라(?) 내 눈에 자주 보이는 비트마스킹

 

모든 조합에 대한 경우의 수를 따질 때 매우 유용하다.

 

 

 

예를 들어서 3개의 재료가 있고, 이 재료들을 섞을 수 있는 모든 조합의 경우를 생각해보자.

 

편의상 각 재료를 a, b, c라고 하자. 답은 아래와 같다.

 

아무 것도 쓰지 않음, a, b, c, ab, ac, bc, abc

 

총 8가지가 나오는데 이 값은 2^3과 같다.

 

 

 

여기서 a, b, c에 대해 사용할 때를 1, 사용하지 않을 때를 0이라고 가정해보자.

 

예를 들어 a만 사용할 때를 001, b만 사용하면 010, c만 사용하면 100이다.

 

당연히 ab를 사용하면 011이 된다. 이렇게 매핑했을 때, 위의 8가지 경우의 수는 다음과 같이 표현할 수 있다.

 

000, 001, 010, 011, 101, 110, 111

 

이것이 비트로 집합을 표현하는 방식이다.

 

 

 

위와 같이 비트로 매핑해서 모든 경우의 수를 따져보는 방식을 사용하려면 우선 모든 경우의 수를 구해야 한다.

 

주어진 2961번 문제와 같은 경우에는 생각보다 간단하다. 재료를 쓰고(1) 혹은 재료를 쓰지 않고(0)의 두가지 뿐이기 때문이다.

 

재료가 5개라면 2^5가지 존재한다.

 

재료가 4개라면 2^4가지 존재한다.

 

재료가 10개라면 2^10가지 존재한다.

 

모든 경우의 수를 코드로 구하면 아래처럼 된다.

int lth = 1<<n;

 

 

 

이제 이 경우의 수만큼 반복문을 돌리면 모든 조합의 경우가 i에 하나씩 저장된다.

for(int i=1; i<lth; ++i){
    
}

 

i=1은 00...001

i=2는 00...010

i=3은 00...011

i=4는 00...100

...

 

(편의상 1을 켜져 있다, 0을 꺼져 있다라고 하겠다.)

 

위처럼 접근하면 되는데, 문제는 어떻게 정수 i의 값으로 몇번째가 켜져있는가를 비트처럼 확인해낼 수 있을까?

 

 

 

여기서 브루트포스가 등장하는데, 아래처럼 재료의 수 n에 대한 for문으로 각 재료를 하나씩 뽑아오면 된다.

for(int i=1; i<lth; ++i){
    for(int j=0; j<n; ++j){
        
    }
}

당연히 j는 각각의 재료들의 번호를 하나씩 뽑아온다.

 

 

 

그리고 아래와 같이 j를 left shift해서 필요한 만큼 2를 곱해준 값과 i를 & 연산한다.

for(int i=1; i<lth; ++i){
    for(int j=0; j<n; ++j){
        if((i & 1<<j) > 0){
            // 해당 비트들이 켜져있을 때, 동작할 로직
        }
    }
}

i를 다시 풀어쓰면 몇번째 비트가 켜져 있고 몇번째 비트가 꺼져 있는지에 대한 정보를 가지고 있다. 

 

j는 각 재료의 번호인데, j만큼 1을 left shift하면 각 재료의 번호에 해당하는 비트만 켜진다.

 

예를 들어보자. (left shift를 한번 할 때마다 "2"를 곱한다는 것에 주의)

 

j=2일 때, 1<<2가 되고 값은 4이고   비트는 0...000100

j=3일 때, 1<<3이 되고 값은 8이고   비트는 0...001000

j=4일 때, 1<<4가 되고 값은 16이고 비트는 0...010000

j=5일 때, 1<<5가 되고 값은 32이고 비트는 0...100000

...

 

당연히 0부터 시작한다고 했을 때 해당 자리만 켜지는 것을 알 수 있다.

 

이 j의 비트 값을 i와 &하면 해당 j번째의 경우가 i에 포함되어 있는지 확인할 수 있다.

 

예를 들어 i가 6이다. (비트 값은 0...110이다.)

j=2일 때 i와 &하면 결과는 4가 나온다. (j=2, 1<<2 → 4)

j=1일 때 i와 &해도 결과는 2가 나오고, (j=1, 1<<1 → 2)

 

물론 j=0일 때 i와 &하면 결과는 0이 나온다. (j=0, 1<<0 → 1)

 

결론적으로 핵심은 몇 번째 비트가 켜져 있는지 알아내기 위해 j만큼 1을 left shift 해주고 i와 &(and)연산 해주는 것이다.

 

 

 

그리고 아래의 if문 내에 있는 0 초과일 때의 조건은 어찌보면 당연하다.

if((i & 1<<j) > 0){

 

j가 i의 경우의 수에 포함되는지만 보면 되는 것이므로 0 (아무것도 매핑되지 않음) 상태는 무시한다.

 

 

 

 

 

 

 

여기까지 핵심이 되는 로직만 따로 뽑아내 보면 아래와 같다.

int lth = 1<<n;
for(int i=1; i<lth; ++i){
    for(int j=0; j<n; ++j){
        if((i & 1<<j) > 0){
            // 해당 비트들이 켜져있을 때, 동작할 로직 ~
        }
    }
}

 

 

 

 

# 문제를 풀기 위한 최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        StringTokenizer st;

        int[][] ingredients = new int[n][2];
        for(int i=0; i<n; ++i){
            st = new StringTokenizer(br.readLine());
            ingredients[i][0] = Integer.parseInt(st.nextToken());
            ingredients[i][1] = Integer.parseInt(st.nextToken());
        }

        // 신 --> 곱, 쓴 --> 합
        int ans = Integer.MAX_VALUE;
        int lth = 1<<n;
        for(int i=1; i<lth; ++i){ // 공집합 제외
            int sour=1, bitter = 0;
            for(int j=0; j<n; ++j){ // 0번째 재료, 1번째 재료...
                if((i & 1<<j) > 0){ // 숫자는 미리 뽑아낸 후, 똑같이 비트로 만들어 접근
                    sour *= ingredients[j][0];
                    bitter += ingredients[j][1];
                }
            }
            int diff = Math.abs(sour - bitter);
            ans = Math.min(ans, diff);
        }

        System.out.print(ans);
    }
}

 

 

 

# 시프트 연산을 줄이기 위해 조금 더 최적화

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        StringTokenizer st;

        int[][] ingredients = new int[n][2];
        for(int i=0; i<n; ++i){
            st = new StringTokenizer(br.readLine());
            ingredients[i][0] = Integer.parseInt(st.nextToken());
            ingredients[i][1] = Integer.parseInt(st.nextToken());
        }

        int[] bits = new int[n];
        for(int i=0; i<n; ++i){
            bits[i] = 1<<i;
        }

        // 신 --> 곱, 쓴 --> 합
        int ans = Integer.MAX_VALUE;
        int lth = 1<<n;
        for(int i=1; i<lth; ++i){ // 공집합 제외
            int sour=1, bitter = 0;
            for(int j=0; j<n; ++j){ // 0번째 재료, 1번째 재료...
                if((i & bits[j]) > 0){ // 숫자는 미리 뽑아낸 후, 똑같이 비트로 만들어 접근
                    sour *= ingredients[j][0];
                    bitter += ingredients[j][1];
                }
            }
            int diff = Math.abs(sour - bitter);
            ans = Math.min(ans, diff);
        }

        System.out.print(ans);
    }
}

 어차피 j의 범위는 n까지이고 같은 수를 만들기 위해 계속 1<<j 를 수행해야 하므로,

 

상단에 미리 시프트된 비트들을 저장하는 배열 int[] bits를 준비해서 재사용한다.

 

속도는 더 빨라지지만 직관적으로 볼 때에 이해는 위에 있는 녀석이 더 빠르려나?

 

 

 

아래 bits 배열에는

00...0001

00...0010

00...0100

... 따위가 저장되어 있다는 것을 외워두고 사용하면 마스킹할 때 요긴할 것 같긴 하다.

for(int i=0; i<n; ++i){
    bits[i] = 1<<i;
}