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

이 문제는 SILVER 1 단계의 백준 문제이다. 

 

입력으로는 N개의 재료와, 각각의 재료에 대해 신맛과 쓴맛이 주어진다.

N개의 재료 중 하나 이상의 재료를 이용해 선택된 재료의 신맛끼리 곱한 값과 쓴맛끼리 더한 값의 차이가 가장 적은 음식을 만들어야 한다.

 

이 문제에서 핵심 코드는 재료의 맛을 계산해 주는 함수인데, 재귀를 이용해서 짰다.

N개의 재료를 가지고 부분집합을 만들어서 모든 부분집합에 대해 신맛과 쓴맛의 차이를 구해주었다. check 배열을 이용해 cnt번째 원소가 부분집합에 들어간다면 true, 들어가지 않는다면 false를 넣어주었다. cnt 가 재료의 갯수와 같아지면 check 배열 중 true 인 원소끼리 계산 해 값을 구하고, 그 중 가장 작은 값을 ans에 넣어 주었다.문제에서 주어진 조건대로 한 개 이상의 재료를 사용해야 하기 때문에 공집합은 빼주어야 하는데, 공집합을 찾아내기 위해서 c라는 변수를 사용했다.  for문을 돌고 나왔을 때 c의 값이 true라면 원소가 한 개 이상 들어있다는 것이기 때문에 c의 값이 true일 때만 계산을 해 주었다.

 

 

static void cook(int cnt) {
		boolean c = false;
		if(cnt == N) {
			int sm = 1; //신맛 초기 값 
			int bm = 0; //쓴맛 초기 값
			for(int i=0; i<N; i++) {
				if(check[i]) {
					sm *= ingredients[i][0]; //신맛 곱하기
					bm += ingredients[i][1]; //쓴맛 더하기
					c = true;
				}
			}
			if(c) {
				int sum = Math.abs(bm-sm);
				if(sum < ans) //총합이 더 작으면 ans에 넣어줌
					ans = sum;
			}
			return;
		}
		
		check[cnt] = true;
		cook(cnt+1);
		check[cnt] = false;
		cook(cnt+1);
	}

 

 

 

전체 코드에서 보면,

BufferedReader를 이용해 값을 받아주고 모든 연산은 cook에서 실행한 뒤 ans 값만 받아주는 것을 볼 수 있다.

 

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

public class Main {
	static int N;
	static int[][] ingredients;
	static boolean[] check;
	static int ans;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		ingredients = new int[N][2];
		check = new boolean[N];
		ans = 1000000000;
		for(int i=0; i<N; i++) {
			String[] s = br.readLine().split(" ");
			ingredients[i][0] = Integer.parseInt(s[0]); //신맛
			ingredients[i][1] = Integer.parseInt(s[1]); //쓴맛
		}
		cook(0);
		System.out.println(ans);
	}
	
	static void cook(int cnt) {
		boolean c = false;
		if(cnt == N) {
			int sm = 1; //신맛 초기 값 
			int bm = 0; //쓴맛 초기 값
			for(int i=0; i<N; i++) {
				if(check[i]) {
					sm *= ingredients[i][0]; //신맛 곱하기
					bm += ingredients[i][1]; //쓴맛 더하기
					c = true;
				}
			}
			if(c) {
				int sum = Math.abs(bm-sm);
				if(sum < ans) //총합이 더 작으면 ans에 넣어줌
					ans = sum;
			}
			return;
		}
		
		check[cnt] = true;
		cook(cnt+1);
		check[cnt] = false;
		cook(cnt+1);
	}
}

 

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