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

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

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

 

* 트리문제 구현방법

 

1.매개변수로 합을 저장할 변수 make

2.재귀호출2개

    1번: 현재값을 계산하고(선택하고) 호출, 요리 카운트++

    2번: 현재값을 (선택안하고) 계산안하고 호출, 요리 카운트그대로

 

참고 : depth가 깊이, 인덱스 역할도 함.

cnt는 입력이 1쌍일때 정답이 무조건 1이되는 현상 방지     [(0,1,0,0)으로 호출하므로 차이가 1임]

cnt(input_count) => 요리횟수저장 ,요리안하고 정답갱신되는거 방지 == 요리1번이상 됐을때만 정답갱신

트리그림에서 공집합 인경우 (모두선택X인경우) 계산을 안해야됨.

	static void rec(int depth,int sin_sum, int ssen_sum, int cnt)
	{

		if(depth==N)
		{
			if(cnt>=1)
				answer=Math.min(Math.abs(sin_sum-ssen_sum),answer);
			return;
		}
		

		rec(depth+1,sin_sum*sin[depth],ssen_sum+ssen[depth],cnt+1);
		
		rec(depth+1,sin_sum,ssen_sum,cnt);

	}

 

 

 

 

 

 

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

public class Main_2961_유동훈 {

	static int N;
	static int[] sin;
	static int[] ssen;
	static int sin_sum=1;
	static int ssen_sum;
	static int answer=Integer.MAX_VALUE;
	
	/*static void print()
	{
		for(int i=0;i<result.length;++i)
		{
			System.out.print(result[i]+" ");
		}
		System.out.println();
	}
	static void copy_arr()
	{
		for(int i=0; i<answer.length;++i)
		{
			answer[i]=result[i];
		}
	}*/
	
	
	
	
	/*
	 * depth가 인덱스역할도 함
	 * cnt(count)=>1회이상일때만 갱신?
	 * 
	 * 
	 * 
	 */
	
	static void rec(int depth,int sin_sum, int ssen_sum, int cnt)
	{
		//sin_sum=1;
		//int ssen_sum=0;
		if(depth==N)
		{
			if(cnt>=1)
				answer=Math.min(Math.abs(sin_sum-ssen_sum),answer);
			return;
		}
		
		
		//sin_sum=sin_sum*sin[depth];
		//ssen_sum=ssen_sum+ssen[depth];
		rec(depth+1,sin_sum*sin[depth],ssen_sum+ssen[depth],cnt+1);
		
		//if(N!=1)
		rec(depth+1,sin_sum,ssen_sum,cnt);

		
	}
	
	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];
		ssen=new int[N];
		for(int i=0;i<N;++i)
		{
			st=new StringTokenizer(br.readLine());
			sin[i]=Integer.parseInt(st.nextToken());
			ssen[i]=Integer.parseInt(st.nextToken());
		}
		//입력 끝
		
		rec(0,1,0,0);
		
		
		
		
		
		StringBuilder sb= new StringBuilder();
		sb.append(answer);
		/*for(int i=0; i<answer.length;++i)
		{
			sb.append(answer[i]+"\n");
		}*/
		System.out.println(sb);
	}

}