알고리즘 - 백준 - 2961 - 도영이가 만든 맛있는 음식 - JAVA

김성일·2024년 9월 14일
BigIntegerJava백준부분 집합실버알고리즘완전 탐색
0

알고리즘

목록 보기
11/23
post-thumbnail
post-custom-banner

문제 바로가기

https://www.acmicpc.net/problem/2961

문제 소개 및 재정의

N개의 재료로 만들수 있는 모든 조합을 구한다.
조합별로 신맛과 쓴맛을 구한뒤 두 맛의 차이를 구한다.
신맛은 재료별로 곱해주고 쓴맛은 재료별로 더해준다.
맛의 차이가 가장 적은것을 제출한다.

문제 패턴

N개의 재료로 만들수 있는 모든 조합을 구해야 한다.
따라서 부분집합을 사용해야한다.
부분집합에서 공집합은 문제에서 제외하라고 한다.
부분집합별로 음식의 두가지 맛을 계산해서 그 차이를 구하고.
최소값과 비교해서 최소값을 업데이트 해준다.

어떻게 풀까? - 완전탐색

포인트

재료 pool에서 부분집합을 재귀적으로 생성했다.
바닥조건에 닿을때마다 boolean 배열로 부분집합이 생성된다.
이때, 배열을 순회하면 값이 true(포함)인 재료들의 맛을 계산해준다.
부분집합마다 음식의 맛을 계산해서 그 차이를 최소값과 비교한다.

최악의 경우
식재료는 10개, 모든 식재료의 쓴맛과 신맛의 값이 10910^9 일수있다.
대략적으로 103=21010^3 = 2^{10} 이므로 이렇게 계산을 하겠다.
.
이 경우 쓴맛은 109∗10=10∗23010^9*10 = 10*2^{30}의 정수값을 가진다.
이 값은 long 타입으로 커버가 가능한 값이다.
사실 int의 최대값을 21억에 근사하므로 100억은 커버 못한다는 사실을 금방 알수있다.
.
신맛의 경우에는 (109)10=1090=2300(10^9)^{10} = 10^{90} = 2^{300}으로 대략 300비트 이상을 저장할수있는 자료형이 필요하다.
long은 64-1비트의 양수까지만 저장할수 있으므로 더 큰 자료형이 필요하다.
그래서 BigInteger 자료형을 사용했다.

BigInteger를 사용하기 위해서 사용한 레퍼런스

전체 코드 - 클린 버전

import java.io.*;
import java.util.*;
import java.math.*;


public class BOJ_2961_도영이가_만든_맛있는_음식 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	// 세팅
	static int N;
	static int[][] origin; // new int[N][2]
	static boolean[] subset;
	static boolean miniIsFirst = true;
	static BigInteger mini;
	
	// 메서드
	// 부분집합 구하기
	static void makeSubset(boolean[] leaf, int nowDigit, final int targetDigit) {
		// 바닥 조건
		if(nowDigit>=targetDigit) {
			// 추가작업
			calc();
			return;
		}
		
		// 재귀 파트
		leaf[nowDigit] = false;		// 미포함
		makeSubset(leaf, nowDigit+1, targetDigit);
		leaf[nowDigit] = true;		// 포함
		makeSubset(leaf, nowDigit+1, targetDigit);
	}
	
	// 각각의 부분집합에서 계산하기
	static void calc() {
		boolean token = false;
		BigInteger S = BigInteger.valueOf(1);
		BigInteger B = BigInteger.valueOf(0);
		
		// 부분집합의 값들 계산
		for(int i=0; i<N; i++) {
			if(subset[i]==false)	
				continue;
			token = true; // 반복문이 끝날때까지 token이 false면 공집함임을 의미함.
			// subset[i]==true일때 로직
			BigInteger Si = BigInteger.valueOf(origin[i][0]);
			BigInteger Bi = BigInteger.valueOf(origin[i][1]);
			S = S.multiply(Si);
			B = B.add(Bi);
		}
		if(token==false)
			return;
		BigInteger gap = B.subtract(S);
		gap = gap.abs(); 
		if(miniIsFirst) {
			mini = gap;
			miniIsFirst = false;
		} else { // 최소값 초기화 성공 이후
			mini = mini.min(gap);
		}
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		N = Integer.parseInt(input.readLine());
		origin = new int[N][2];
		for(int i=0; i<N; i++) {
			tokens = new StringTokenizer(input.readLine());
			int Si = Integer.parseInt(tokens.nextToken());
			int Bi = Integer.parseInt(tokens.nextToken());
			origin[i][0] = Si;
			origin[i][1] = Bi;
		}
		subset = new boolean[N];
		// 세팅
		// 작업
		makeSubset(subset, 0, N);
		// 출력
		System.out.println(mini);
	}

}

전체 코드 - 주석 버전

import java.io.*;
import java.util.*;
import java.math.*;


public class BOJ_2961_도영이가_만든_맛있는_음식 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	// 세팅
	static int N;
	static int[][] origin; // new int[N][2]
	static boolean[] subset;
	static boolean miniIsFirst = true;
	static BigInteger mini;
	
	// 메서드
	// 부분집합 구하기
	static void makeSubset(boolean[] leaf, int nowDigit, final int targetDigit) {
		// 바닥 조건
		if(nowDigit>=targetDigit) {
			// 추가작업
			calc();
			return;
		}
		
		// 재귀 파트
		leaf[nowDigit] = false;		// 미포함
		makeSubset(leaf, nowDigit+1, targetDigit);
		leaf[nowDigit] = true;		// 포함
		makeSubset(leaf, nowDigit+1, targetDigit);
	}
	
	// 각각의 부분집합에서 계산하기
	static void calc() {
		// 처음값 넣기 위함.
		
		// 신맛과 쓴맛은 자연수이기 때문에 처음에 0으로 시작해도 된다. 마지막에도 값이 0이면 공집합이라는 뜻이므로 버린다. 
		// => 그렇지 않다. 쓴맛은 곱하기이므로 1부터 시작해야한다. 공집합 처리는 그냥 token을 사용하자.
		// => 쓴맛이 합이고 신맛이 곱이다... 반대로 착각하는 이슈가 있었다...
		boolean token = false;
		BigInteger S = BigInteger.valueOf(1);
		BigInteger B = BigInteger.valueOf(0);
		
		// 부분집합의 값들 계산
		for(int i=0; i<N; i++) {
			if(subset[i]==false)	// 코드 가독성을 위해서 인덴트 뎁스를 낮추는 차원에서 false일때 버린다. true일때 계산하기 위해서
				continue;
			token = true; // 반복문이 끝날때까지 token이 false면 공집함임을 의미함.
			// subset[i]==true일때 로직
			BigInteger Si = BigInteger.valueOf(origin[i][0]);
			BigInteger Bi = BigInteger.valueOf(origin[i][1]);
			S = S.multiply(Si); 		// 계산 값을 S에 다시 저장 안해줘서 gap이 1만 나오는 이슈가 있었음... BigInteger 낯설다...
			B = B.add(Bi);	// 계산 값을 B에 다시 저장 안해줘서 gap이 1만 나오는 이슈가 있었음... BigInteger 낯설다...
		}
		if(token==false) // 공집합 버림 token ==true일때 버렸던 이슈가 있었음... 단순 착오
			return;
		BigInteger gap = B.subtract(S); // B는 곱하기로 커지고 S는 더하기로 커지므로 무조건 B가 더 크다. => 반례가 있을지도 모르니 속 편하게 절대값 구하자.
		gap = gap.abs(); // 절대값을 gap에 저장해주지 않는 이슈가 있었다...
//		System.out.println(S+" | "+ B+" | "+gap +" | "+mini);
		if(miniIsFirst) {
			mini = gap;
			miniIsFirst = false;
		} else { // 최소값 초기화 성공 이후
			mini = mini.min(gap);
		}
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		N = Integer.parseInt(input.readLine());
		origin = new int[N][2];
		for(int i=0; i<N; i++) {
			tokens = new StringTokenizer(input.readLine());
			int Si = Integer.parseInt(tokens.nextToken());
			int Bi = Integer.parseInt(tokens.nextToken());
			origin[i][0] = Si;
			origin[i][1] = Bi;
		}
		subset = new boolean[N];
		// 세팅
		// 작업
		makeSubset(subset, 0, N);
		// 출력
		System.out.println(mini);
	}

}

퍼포먼스

[ 12,840 KB | 76 ms ]

마무리

문제를 끊김없이 푼게 아니고 문제를 읽어두고, 다음날 코드를 짰다.
그러다보니 문제를 잘못 이해한 이슈가 조금 있었다.
BigInteger 사용이 어색해서 값을 저장하는 것을 깜빡하는 이슈가 있었다.

시간이 제일 짧은 자바코드를 보니까 음식의 신맛과 쓴맛을 int타입에 저장해서 풀었다.
저렇게해서 풀릴거면 입력을 왜 저렇게 만들었을까?
테스트가 충분하지 않은 문제라는 생각이 들었다.

profile
김성일
better을 통해 best로
이전 포스트

알고리즘 - 백준 - 1541 - 잃어버린 괄호 - JAVA

다음 포스트

알고리즘 - 백준 - 14891 - 톱니바퀴 - JAVA

post-custom-banner

0개의 댓글