λ°±μ€ 2961λ² - λμμ΄κ° λ§λ λ§μλ μμ
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);
}
}