import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, sour = 1, bitter, minDiff = Integer.MAX_VALUE, tmpDiff;
static int[][] pairs;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st;
pairs = new int[n][2];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
pairs[i] = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
}
for (int r = 1; r <= n; r++) {
combination(0, 0, r);
}
System.out.println(minDiff);
}
private static void combination(int cnt, int start, int r) {
if (cnt == r) {
tmpDiff = Math.abs(sour - bitter);
if (tmpDiff < minDiff) {
minDiff = tmpDiff;
}
return;
}
for (int i = start; i < n; i++) {
sour *= pairs[i][0];
bitter += pairs[i][1];
combination(cnt + 1, i + 1, r);
sour /= pairs[i][0];
bitter -= pairs[i][1];
}
}
}
조합의 합이 어차피 부분 집합이니까 간단하게 작성한 코드
bit masking으로 다시 풀어보자
비트 마스킹 + 부분 집합 버전
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, sour, bitter, minDiff = Integer.MAX_VALUE, i;
static int[][] pairs;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st;
pairs = new int[n][2];
for (i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
pairs[i] = new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
}
subSet(0, 0);
System.out.println(minDiff);
}
private static void subSet(int cnt, int flag) { // selected 배열 대신 flag를 통해 사용 여부 체크
if (cnt == n) {
if (flag == 0) // 아무것도 선택하지 않는 경우 즉, flag = 0일 때
return;
sour = 1;
bitter = 0;
for (i = 0; i < n; i++) {
if ((flag & 1 << i) != 0) {
sour *= pairs[i][0];
bitter += pairs[i][1];
}
}
minDiff = Math.min(Math.abs(sour - bitter), minDiff);
return;
}
subSet(cnt + 1, flag | 1 << cnt); // cnt depth만큼 bit shift 수행해서 선택 여부 check
subSet(cnt + 1, flag); // 선택하지 않는 경우의 수도
}
}
'온라인 저지 > BOJ' 카테고리의 다른 글
[BOJ/Java] 20361 일우는 야바위꾼 (0) | 2022.02.14 |
---|---|
[BOJ/Java] 20299 3대 측정 (0) | 2022.02.14 |
[BOJ/Java] 12927 배수 스위치 (0) | 2022.02.13 |
[BOJ/Java] 5430 AC (0) | 2022.02.13 |
[BOJ/Java] 1874 스택 수열 (0) | 2022.02.13 |
댓글