[BAEKJOON] 2961 도영이가 만든 맛있는 음식 (Java)

[ 문제 ]

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

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

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

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

입력

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

출력

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

[ 핵심풀이 ]

1개~N개 까지 조합을 찾고, 쓴맛과 신맛의 차이를 구해주면된다

중복에 대해 배제하지않아주어도 널널하지만, 중복 조합을 찾지않도록 소스코드를 해주는게 실력에 도움이될것이다.

전체소스는 중복을 제외하지않은 조합.

핵심소스는 중복을 제외한 조합이므로 참고바란다.

[ 핵심소스 ]

static void solve(int index, int cnt) {
    if (Cnt==cnt) {
        int temp = sub();
        Value = Value < temp ? Value:temp;
        return;
    }
    for(int i=index;i<N;i++) {
        if (!visit[i]) {
            visit[i]=true;
            ary[cnt]=i;
            solve(index+1, cnt+1);
            visit[i]=false;
        }
    }
}

[ Java ]

import java.util.Scanner;

class Data {
    int sin;
    int sen;
    Data(int sin, int sen) {
        this.sin=sin;
        this.sen=sen;
    }
}
public class _2961_도영이가_만든_맛있는_음식 {
    static final int MAX = 11;
    static int N;
    static int Cnt;
    static int Value = Integer.MAX_VALUE;
	
    static Data dish[] = new Data[MAX];
    static int ary[] = new int[MAX];
    static boolean visit[] = new boolean[MAX];
    static void solve(int cnt) {
        if (Cnt==cnt) {
            int temp = sub();
            Value = Value < temp ? Value:temp;
            return;
        }
        for(int i=0;i<N;i++) {
            if (!visit[i]) {
                visit[i]=true;
                ary[cnt]=i;
                solve(cnt+1);
                visit[i]=false;
            }
        }
    }
    static int sub() {
        int sin_sum=1;
        int sen_sum=0;
        for(int i=0;i<Cnt;i++) {
            sin_sum*= dish[ary[i]].sin;
            sen_sum+= dish[ary[i]].sen;
        }
        return Math.abs(sin_sum-sen_sum);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for(int i=0;i<N;i++)
            dish[i] = new Data(sc.nextInt(), sc.nextInt());
        for(int i=1;i<=N;i++) {
            Cnt = i;
            solve(0);
        }
        System.out.println(Value);
    }
}