백준 2961번: 도영이가 만든 맛있는 음식
문제 설명
- 조건을 만족하는
적절한 조합
을 찾는 문제입니다.
접근법
- 재료의 개수가 적기 때문에
부분집합
으로 풀 수 있습니다.- 부분집합은
해당 값 선택 + 재귀함수
그리고해당 값 선택X + 재귀함수
를 통해 구현할 수 있습니다. - 선택X를 food(1,0)으로 설정했습니다.
- 선택 or 선택X가 반드시 들어오기 때문에 depth ==N일때 종료하면 됩니다.
- 부분집합은
- 신맛과 쓴맛의 값을 담기 위해 food class를 생성했습니다.
정답
import java.util.*;
public class Main {
static int N;
static food[] s; // 입력으로 들어오는 재료를 담는 변수입니다.
static food[] answer; // 부분집합으로 만든 결과를 담는 변수입니다.
static int min_val = 1; //(1,0),(0,0)인 경우도 생각해보면 1이 가장 적절한 초기값입니다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = Integer.parseInt(sc.nextLine());
s = new food[N];
answer = new food[N];
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(sc.nextLine()," ");
s[i] = new food(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
}
subset(0);
System.out.println(min_val);
}
public static void subset(int depth) {
if(depth == N) {
int S_sum = 1;
int B_sum = 0;
for (int i = 0; i < N; i++) {
S_sum*=answer[i].S;
B_sum+=answer[i].B;
}
// 재료를 하나도 사용하지 않은 경우
if(S_sum == 1 && B_sum == 0)return;
min_val = Math.min(min_val, Math.abs(S_sum-B_sum));
return;
}
//depth번째 값을 선택합니다.
answer[depth] = s[depth];
subset(depth+1);
//depth번째 값을 선택하지 않습니다.
answer[depth] = new food(1,0);
subset(depth+1);
}
}
class food{
int S;
int B;
public food(int S , int B) {
this.S = S;
this.B = B;
}
@Override
public String toString() {
return "food [S=" + S + ", B=" + B + "]";
}
}
Author And Source
이 문제에 관하여(백준 2961번: 도영이가 만든 맛있는 음식), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-2961번-도영이가-만든-맛있는-음식저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)