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

풀이

---

해당 백준 문제에서 알고리즘 분류로 '브루트포스 알고리즘'과 '비트마스킹'이라는 것이 힌트로 나와있길래 비트마스킹을 사용하여 문제를 해결하였다.

 

BitArrayBuilder 라는 클래스를 따로 만들어주어서 생성자로 비트 열의 사이즈를 정하도록 되어있는데, 도영이의 재료 N개를 의미한다.

 

'마스킹' 이라하면 여러 군데 특히 포토샵을 조금 써보신 분들이라면 익숙하실 탠데, 마스킹(Masking) 기법은 어떤 배열을 대상으로 하여 배열 내 모든 값들 중 특정한 조건을 만족하는 것들만 선별하는 기법이다.

 

이걸 어떻게 사용했었냐면, 비트가 1에 위치한 것들만 추출하여 계산하여 최솟값을 찾는 방법을 택했다. 4비트라고 했을 때, 우리는 0000~1111까지 서로 겹치지 않는 방법으로 모든 것을 확인할 수 있다. 0000, 0001, 0010, .... , 1111

 

 

예시

---

사이트 예제3) N = 4 일 때

 

비트가 1000 이라면,

S B | 비트마스크

1 7 | 1

2 6 | 0

3 8 | 0

4 9 | 0

1 7 만 뽑혔으니 서로 빼서 최솟값으로 저장

 

비트가 1010 이라면,

S B | 비트마스크

1 7 | 1

2 6 | 0

3 8 | 1

4 9 | 0

1 7 과 3 8이 뽑혔으니 1과 3은 곱하고(S) 7과 8은 더해서(B) 서로 뺀 다음 방금 전의 최솟값과 비교

 

이런 식으로 0000부터 1111까지 계산한 다음 최솟값을 출력하면 정답이다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        //필요한 변수들
        int size = 0;
        ArrayList<Integer> S = new ArrayList<Integer>();
        ArrayList<Integer> B = new ArrayList<Integer>();
        int min = Integer.MAX_VALUE;

        //사용자 값 입력받기
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        size = Integer.parseInt(reader.readLine());
        for (int i = 0; i < size; i++) {
            String tmp = reader.readLine();
            String[] strTmp = tmp.split(" ");

            S.add(Integer.parseInt(strTmp[0]));
            B.add(Integer.parseInt(strTmp[1]));
        }


        // 여기서 부터 알고리즘 시작
        BitArrayBuilder bitArrayBuilder = new BitArrayBuilder(size);

        for (int i = 1; i <= bitArrayBuilder.getMaxValue(); i++) {
            ArrayList<Byte> tmp = bitArrayBuilder.getBitArray(i);

            int mulS = 1;
            int mulB = 0;

            for (int j = 0; j < tmp.size(); j++) {
                if(tmp.get(j)!=0){
                    mulS *= S.get(j);
                    mulB += B.get(j);
                }
            }

            int result = Math.abs((mulS - mulB));
            if(min > result){
                min = result;
            }
        }

        System.out.println(min);

    }
}

class BitArrayBuilder{
    int size;

    BitArrayBuilder(int size){
       this.size = size;
    }

    public void setSize(int size){
        this.size = size;
    }

    public int getSize(){
        return this.size;
    }
    ArrayList<Byte> getBitArray(int value){

        if(value>getMaxValue()){
            System.out.println("허용범위 초과!");
            return null;
        }

        ArrayList<Byte> tmp = new ArrayList<Byte>();
        for (int i = 0; i < this.size; i++) {
            tmp.add(Byte.parseByte("0"));
        }

        int val = value;

        int i = 0;
        while(val!=0){
            int remain = val % 2;
            val = val / 2;

            if(remain == 0){
                tmp.set(i, Byte.parseByte("0"));
            }else{
                tmp.set(i, Byte.parseByte("1"));
            }

            i++;
        }
        return tmp;
    }

    int getMaxValue(){
        int sum = 1;
        for (int i = 1; i < this.size; i++) {
            int tmp = 1;
            for (int j =0; j<i ; j++){
                tmp = tmp * 2;
            }
            sum += tmp;
        }

        return sum;
    }
}