BJ2961 도영이가 만든 맛있는 음식
https://www.acmicpc.net/problem/2961
조합을 이용해 각 음식의 쓴 맛과 신 맛을 합연산과 곱연산으로 계산하여 두 값의 최소값을 출력하는 문제이다.
조합을 재귀함수로 구현할 수 있다면 쉽게 해결할 수 있다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, R, minGap, multi, sum; // 차이, 곱(신맛), 합(쓴맛).
static int[][] input;
static int[] numbers;
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
public static void combination(int cnt, int start) { // 현재 자리에 수 뽑기.
if(cnt == R) {
int gap = Math.abs(multi - sum);
if(gap < minGap) {
minGap = gap;
}
//System.out.println(Arrays.toString(numbers));
return;
}
// 입력받은 모든 수를 현재 자리에 넣어보기(유도파트)
for(int i = start; i < N; i++) {
multi *= input[i][0];
sum += input[i][1];
combination(cnt + 1, i + 1);
multi /= input[i][0];
sum -= input[i][1];
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
input = new int[N][2];
numbers = new int[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
input[i][0] = Integer.parseInt(st.nextToken());
input[i][1] = Integer.parseInt(st.nextToken());
}
minGap = Math.abs(input[0][0] - input[0][1]);
for(int i = 1; i <= N; i++) {
multi = 1;
sum = 0;
R = i;
combination(0, 0);
}
System.out.println(minGap);
}
}
Author And Source
이 문제에 관하여(BJ2961 도영이가 만든 맛있는 음식), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/BJ2961-도영이가-만든-맛있는-음식저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)