1. 문제
2961번: 도영이가 만든 맛있는 음식
첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은
www.acmicpc.net
도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.
지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.
시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.
재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.
2. 풀이
모든 경우의 수를 체크하되, 각각의 자리수가 1인지 아닌지 체크해서(비트마스크) 1이면 그 재료를 넣었다는 뜻이다. 두 번 풀어서 두 가지 버전의 풀이가 있다.
부분집합 메서드 이용
메인
1. 재료를 입력받는다.
2. 재료 고르는 메서드를 호출한다.
3. 답을 출력한다.
static int N;
static int[][] ingredient;
static int MIN = 1_000_000_000;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
ingredient = new int[N][2];
StringTokenizer st;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
ingredient[i][0] = Integer.parseInt(st.nextToken());
ingredient[i][1] = Integer.parseInt(st.nextToken());
}
choose(0,0);
System.out.println(MIN);
}
재료 고르기
비트마스킹을 응용한 부분집합 메서드다. idx==N이고 choice>0일 때 MIN값과 cook메서드 반환값을 비교하고 갱신한다.
public static void choose(int choice, int idx){
if(idx==N){
if(choice == 0) return;
MIN = Math.min(MIN, cook(choice));
return;
}
choose(choice, idx+1);
choose(choice|1<<idx, idx+1);
}
신맛, 쓴맛 차이 구하기
1. 비트마스킹 된 숫자를 받아서 &연산을 이용해 그 재료를 뽑았는지 확인한다.
2. 뽑았다면 신맛에 곱하고 쓴맛엔 더한다.
3. 마지막에 그 차이를 출력한다.
public static int cook(int choice){
int sour = 1;
int bitter = 0;
for(int i=0;i<N;i++){
if((choice&(1<<i)) == 0) continue;
sour *= ingredient[i][0];
bitter += ingredient[i][1];
}
return Math.abs(sour-bitter);
}
전체 코드
import java.io.*;
import java.util.*;
public class BOJ_2961_도영이가만든맛있는음식 {
static int N;
static int[][] ingredient;
static int MIN = 1_000_000_000;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
ingredient = new int[N][2];
StringTokenizer st;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
ingredient[i][0] = Integer.parseInt(st.nextToken());
ingredient[i][1] = Integer.parseInt(st.nextToken());
}
choose(0,0);
System.out.println(MIN);
}
public static void choose(int choice, int idx){
if(idx==N){
if(choice == 0) return;
MIN = Math.min(MIN, cook(choice));
return;
}
choose(choice, idx+1);
choose(choice|1<<idx, idx+1);
}
public static int cook(int choice){
int sour = 1;
int bitter = 0;
for(int i=0;i<N;i++){
if((choice&(1<<i)) == 0) continue;
sour *= ingredient[i][0];
bitter += ingredient[i][1];
}
return Math.abs(sour-bitter);
}
}
반복문 이용
2^N은 N으로 만들 수 있는 모든 경우의 수(공집합 뺌)를 구할 수 있다. 따라서 1부터 2^N까지 탐색하면서 쓴맛, 신맛의 차이를 구한다.
import java.io.*;
import java.util.*;
public class BOJ_2961_도영이가만든맛있는음식 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(in.readLine());
int[][] items = new int[N][2];//0 신맛 1 쓴맛
int diff = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
items[i][0] = Integer.parseInt(st.nextToken());
items[i][1] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i < 1 << N; i++) {//2^N--> 모든 경우의 수
int S = 1, B = 0;
for (int j = 0; j < N; j++) { // 0001 0010 0100 1000
if ((i & 1 << j) != 0) {
S *= items[j][0];
B += items[j][1];
}
}
diff = Math.min(diff, Math.abs(S - B));
}
System.out.println(diff);
}
}
3. 결과
1년 전에는 반복문으로 풀었고, 오늘은 부분집합 메서드를 이용해서 풀었다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 2839 설탕배달 - JAVA (1) | 2023.05.21 |
---|---|
[BOJ] 2206 벽 부수고 이동하기 - JAVA (0) | 2023.05.21 |
[BOJ] 9465 스티커 - JAVA (0) | 2023.05.19 |
[BOJ] 11657 타임머신 - JAVA (0) | 2023.05.18 |
[BOJ] 2636 치즈 - JAVA (1) | 2023.05.17 |
댓글