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

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

해설

방문배열 boolean v[] 를 이용하여 방문체크를 하고, 해당 재료를 선택했을 때와 선택하지 않았을 경우의 신맛과 쓴맛의 차이를 생각해 보면서 차의 최댓값을 구할 수 있도록 하였다.

풀이(java)

package com.ssafy.recursive;

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

class Gredient{
    int sin; // 신맛
    int ssun; // 쓴맛
}

// 백준 2961 도영이가 만든 맛있는 음식
public class Question4my {

    static Gredient[] greds; // 음식 배열
    static int N;
    static int answer=Integer.MAX_VALUE;

public static void main(String[] args) throws Exception {
    // TODO Auto-generated method stub
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    StringTokenizer st;
    greds = new Gredient[N];
    
    for(int i=0;i<N;i++) {
        st = new StringTokenizer(br.readLine());
        greds[i] = new Gredient();
        greds[i].sin = Integer.parseInt(st.nextToken());
        greds[i].ssun = Integer.parseInt(st.nextToken());
    }
    
    yori(0, new boolean[N]);
    System.out.println(answer);

}
// 조합? 
private static void yori(int idx, boolean[] v) {
    int sin=1; // 곱해야 하므로 초기값 1
    int ssun=0; // 더해야 하므로 초기값 0
    if(idx==N) {
        for(int i=0;i<N;i++) {
            if(v[i]) {
                sin*=greds[i].sin;
                ssun+=greds[i].ssun;
            }
        }
        if(sin==1 && ssun==0) return; // 한게 없으면 그냥 리턴
        answer=Math.min(answer, Math.abs(sin-ssun)); // 있으면 차의 최솟값으로 만들기
        return;
    }
    
    v[idx]=true;
    yori(idx+1, v); // idx의 재료 선택
    v[idx]=false;
    yori(idx+1, v); // idx의 재료 미선택
    
	}
}