[백준] 2961번:도영이가 만든 맛있는 음식 (Java 자바)

문제

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

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

 

풀이 및 소스코드

 

재귀를 돌려주는데 신맛은 곱하기라 초기값을 1로 설정해줘야하는데 0으로 해서 헤맸다 .. 하하

재귀를 통해서 모든 경우의 수를 다 탐색한다.

1번 재료 넣어, 안넣어

2번 재료 넣어, 안넣어

이런식으로 재귀를 돌리고, 재료를 넣으면 input_cnt 를 1 증가시킨다.

n번 재료까지 탐색이 완료되고 하나의 재료라도 넣었다면(input_cnt!=0) 비교해서 작은 값을 res에 넣어주었다.

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

public class Main {
	static int[] sin; //곱
	static int[] ss; //합
	static int res = Integer.MAX_VALUE;
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n=Integer.parseInt(br.readLine());
		sin = new int[n];
		ss = new int[n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			sin[i] = Integer.parseInt(st.nextToken());
			ss[i] = Integer.parseInt(st.nextToken());
			
		}
		making_food(0, 0, 1, 0);
		System.out.println(res);
	}
	public static void making_food(int input_cnt, int cnt, int sin_sum, int ss_sum) {
		if(cnt == n) {
			if(input_cnt !=0) {
				res = Math.min(res, Math.abs(sin_sum-ss_sum));
			}
			return;
		}
		making_food(input_cnt, cnt+1, sin_sum, ss_sum); //cnt번째 있는 재료 넣지 않은 것
		making_food(input_cnt+1, cnt+1, sin_sum*sin[cnt], ss_sum+ss[cnt]);
		
	}

}