Algorithm/λ°±μ€€

λ°±μ€€ 2961번 - λ„μ˜μ΄κ°€ λ§Œλ“  λ§›μžˆλŠ” μŒμ‹

giraffe_ 2022. 8. 16. 10:32

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

 

2961번: λ„μ˜μ΄κ°€ λ§Œλ“  λ§›μžˆλŠ” μŒμ‹

첫째 쀄에 재료의 개수 N(1 ≤ N ≤ 10)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개 μ€„μ—λŠ” κ·Έ 재료의 μ‹ λ§›κ³Ό 쓴맛이 곡백으둜 κ΅¬λΆ„λ˜μ–΄ μ£Όμ–΄μ§„λ‹€. λͺ¨λ“  재료λ₯Ό μ‚¬μš©ν•΄μ„œ μš”λ¦¬λ₯Ό λ§Œλ“€μ—ˆμ„ λ•Œ, κ·Έ μš”λ¦¬μ˜ μ‹ λ§›κ³Ό 쓴맛은

www.acmicpc.net

 

 

 

 

 

λ°°λ‚­ 문제 μœ ν˜•μ΄λ‹€. λ°°λ‚­ λ¬Έμ œλŠ” μž¬κ·€λ₯Ό μ΄μš©ν•œ λΆ€λΆ„μ§‘ν•© μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•œλ‹€.

 

 μ‹ λ§›κ³Ό 쓴맛은 2차원 배열을 μ΄μš©ν•˜μ—¬ μ €μž₯ν–ˆλ‹€.

그리고 μž¬κ·€μ˜ λ§€κ°œλ³€μˆ˜λ‘œ μŒμ‹μ˜ μ‹ λ§›κ³Ό 쓴맛을 λ…κ²¨μ€˜ λˆ„μ μœΌλ‘œ κ³„μ‚°ν•˜λ„λ‘ ν–ˆλ‹€.

 

μŒμ‹μ„ λ„£μ—ˆμ„ λ•Œμ™€ μ•ˆλ„£μ—ˆμ„ 경우. 두 κ°€μ§€μ˜ 경우λ₯Ό μž¬κ·€λ‘œ λŒλ¦¬λ„λ‘ ν–ˆλ‹€.

κ·ΈλŸ¬λ‹€κ°€ Nλ²ˆμ„ λ‹€ νƒμƒ‰ν•˜λ©΄ 차이λ₯Ό ꡬ해 μ΅œμ†Ÿκ°’μ„ κ°±μ‹ ν•˜λ„λ‘ ν–ˆλ‹€. μ΄λ•Œ 아무것도 μ•ˆμ“°λŠ” κ²½μš°λŠ” μ œμ™Έν•΄μ•Ό ν•œλ‹€.

 

긜고 또 μ£Όμ˜ν•  점은 쓴맛은 κ³±ν•˜κΈ°λ₯Ό ν•˜λ―€λ‘œ μ΄ˆκΈ°κ°’μ΄ 0 μ•„λ‹ˆλΌ 1둜 μ‹œμž‘ν•΄μ•Ό ν•œλ‹€.

 

 

 

 

μ½”λ“œ

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

public class Main {
	static int N;
	static int[][] dish;
	static int min = 1000000000;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		dish = new int[N][2]; //μ‹ λ§›, μ“΄λ§›
		
		for(int i =0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			dish[i][0] = Integer.parseInt(st.nextToken());
			dish[i][1] = Integer.parseInt(st.nextToken());
		}
		
		subset(0, 1, 0); //μ“΄ 맛은 κ³±ν•˜κΈ°λΌμ„œ 1둜 μ΄ˆκΈ°κ°’ 해야함
		
		System.out.println(min);

	}

	public static void subset(int depth, int sour, int bitter) {
		if(depth == N) {
			if(sour != 1 && bitter != 0) { //아무것도 μ‚¬μš© μ•ˆν•˜λŠ” 경우 μ œμ™Έ
				int d = Math.abs(sour - bitter);
				min = Math.min(min, d);
			}
			
			return;
		}
		
		subset(depth + 1, sour * dish[depth][0], bitter + dish[depth][1]);
		subset(depth + 1, sour, bitter);
	}

}

 

 

 

 

 

 

κ²°κ³Ό