<aside> 📌 2691 도영이가 만든 맛있는 음식
문제
도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.
지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.
시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.
재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.
입력
첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.
출력
첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.
</aside>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
class Main {
static int N;
static int[][] SB;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
SB = new int[N][2];
for (int i = 0; i < N; i++) {
SB[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
if (N == 1) {
System.out.println(Math.abs(SB[0][0] - SB[0][1]));
return;
}
dfs(0, 1, 0);
System.out.println(min);
}
private static void dfs(int depth, int sour, int bit) {
if (depth == N) {
if (Math.abs(sour - bit) < min) min = Math.abs(sour - bit);
return;
}
dfs(depth + 1, sour * SB[depth][0], bit + SB[depth][1]);
dfs(depth + 1, sour, bit);
}
}
지난번에 했던 부분수열 합 문제랑 똑같이 dfs로 해보려고 했는데 틀렸다ㅎ…
하나도 선택을 안 하고 dfs 메소드 호출이 끝날 수도 있나…? ㅏㅇ 그럴 수도 있네,,,
baekjoon/baekjoon2961/Main.java at main · making-a-scene/baekjoon
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
class Main {
static int N;
static int[][] SB;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
SB = new int[N][2];
for (int i = 0; i < N; i++) {
SB[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
dfs(0, 1, 0, 0);
System.out.println(min);
}
private static void dfs(int depth, int sour, int bit, int count) {
if (depth == N) {
if (count != 0 && Math.abs(sour - bit) < min) min = Math.abs(sour - bit);
return;
}
dfs(depth + 1, sour * SB[depth][0], bit + SB[depth][1], count + 1);
dfs(depth + 1, sour, bit, count);
}
}
문제에서 적어도 하나의 재료는 골라야 한다고 했는데, 나는 그냥 재귀 호출만 하면 하나도 안 골라지는 경우는 없을 거라고 생각했다. 근데 잘 생각해보니까 있네ㅎ…. dfs(depth + 1, sour, bit, count);만 계속 호출된 경우에는 sour과 bit 값에 전혀 변화가 없으니 결국 초기 값인 0과 1이 그대로 출력된다. 결국에는 어떤 재료를 선택했을 때마다 count 값을 1 증가시키는 식으로 재료 선택 횟수를 기록하고, 한 번도 재료를 선택하지 않아 count 값이 0인 때는 결과에 반영하지 않아야 한다.
재료의 개수인 N만큼의 depth로 재귀 호출을 하기 때문에 시간 복잡도는 O(N)일 것 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n,res = Integer.MAX_VALUE;
static int[] s,b;
static int solve() throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
s = new int[n+1];
b = new int[n+1];
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
s[i] = Integer.parseInt(st.nextToken());
b[i] = Integer.parseInt(st.nextToken());
}
for (int i=1; i<(1 << n); i++) { // 00001000 n이 3이면 1에서 7까지.
int ts=1, tb=0;
for (int j=0; j<n; j++) { // n이 3이면 0에서 2까지.
if((i & (1 << j)) != 0) { // i와 2^n을 비트끼리 and 연산한 결과 동시에 1인 비트가 없었다면?
ts *= s[j];
tb += b[j];
}
}
res = Math.min(res, Math.abs(ts-tb));
}
return res;
}
public static void main(String[] args) throws IOException {
System.out.println(solve());
}
}
for (int i=1; i<(1 << N); i++) { // n이 3이면 i 값은 1에서 7까지 증가.
int ts=1, tb=0;
for (int j=0; j<N; j++) { // j번째 재료
if((i & (1 << j)) != 0) { // i번째 경우에 j번째 재료는 포함시켜야 하는가?
ts *= s[j];
tb += b[j];
}
}
백준 2961 도영이가 만든 맛있는 음식 java (brute force, bit masking)
비트 마스킹을 이용하면, 비트 연산으로 집합을 표현할 수 있다고 한다.
이 문제에서 재료 N개 중 선택하는 모든 경우의 수는 2^N이고, 하나도 선택 안 하는 경우는 제외해야 하므로 최종적으로는 2^N - 1이 된다. 위 코드의 첫 번째 for문에서 i를 (1 << N) - 1까지 증가시킨 건 이 2^N - 1가지 각각의 경우의 수를 의미하는 것이다. 1을 왼쪽으로 한 번 shift할 때마다 2가 곱해지니까… 1 << N은 결국 2^N라는 뜻이다.