[백준 Silver 1] 2961 도영이가 만든 맛있는 음식 - Java

문제링크 : https://www.acmicpc.net/problem/2961

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

 

접근 과정 : 

• 재료의 조합을 만들어가면서, 각 조합의 신맛과 쓴맛을 계산해 그 차이를 갱신한다.
• 완전탐색을 통해 모든 조합을 확인.
• 사용되는 재료는 비스마스킹으로 체크.
• 아무것도 사용하지 않은 경우를 제외한, 나머지 조합으로 맛의 차이 계산

 

소스 코드 및 결과 :

package BOJ;

/* 
    도영이가 만든 맛있는 음식
*/

import java.io.*;
import java.util.*;

public class BOJ2961 {

    public static void main(String[] args) throws NumberFormatException, 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++) {
            st = new StringTokenizer(br.readLine());

            taste[i][0] = Integer.parseInt(st.nextToken());
            taste[i][1] = Integer.parseInt(st.nextToken());
        }

        diff = 1000000000;

        cook(0, 0, 1, 0);

        System.out.println(diff);
    }

    static int N;
    static int[][] taste;
    static int diff;

    static void cook(int index, int bit, int sour, int bitter) {

        if (index == N) {

            if (bit == 0) {
                return;
            }

            diff = Math.min(diff, Math.abs(sour - bitter));

            return;
        }

        cook(index+1, bit, sour, bitter);
        cook(index+1, bit | (1<<index), sour*taste[index][0], bitter+taste[index][1]);

    }

}

 

P.S 

비트마스킹 유형의 문제를 찾아서 풀었다.

근데.. 해당 문제는 비트마스킹을 굳이 사용하지 않아도 될 것 같은데...

그냥 아무것도 사용하지 않은 경우만 제외해주면 되는거라..