https://www.acmicpc.net/problem/2961
첫번시도에서 통과 했는데 코드 정리하다보니 최적화를 더 할 수 있을거 같아서 두번째 시도에서 시간을 많이 단축하였다. 완전탐색에서 중복재료선택을 줄였다.
재료가 3개면, 완전탐색을 통해 3개중 1개만 사용하는 경우, 2개 사용하는 경우, 3개 사용하는 경우를 다 구해주고 케이스마다 신맛 단맛의 차이를 계산해서 풀었다
예를 들어 재료가 1,2,3 이라고 해보자 그러면
1
2
3
1,2
1,3
2,3
1,2,3
7가지 테스트케이스가 나온다.
import java.io.*;
import java.util.*;
public class Main {
static class Ingredient
{
int ingID;//재료의 고유번호. 최적화 위해 필요.
int bitter;//쓴맛
int sour;//신맛
public Ingredient(int sour, int bitter, int ingID) {
this.sour = sour;
this.bitter = bitter;
this.ingID = ingID;
}
}
static int IngredientCnt;
static ArrayList<Ingredient> list = new ArrayList<>();
static boolean[] checked = new boolean[10];
static Ingredient[] food = new Ingredient[10];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
IngredientCnt = Integer.parseInt(br.readLine());
String[] input;
for(int i =0; i < IngredientCnt; ++i)
{
input = br.readLine().split(" ");
list.add(new Ingredient(Integer.parseInt(input[0]), Integer.parseInt(input[1]), i));
}
int answer = Integer.MAX_VALUE;
for(int i = 1; i < IngredientCnt+1; ++i)
{
clearFood(i);
answer = Math.min(answer, search(0, i));
}
System.out.println(answer);
}
static void clearFood(int targetlevel)//초기화하지 않으면 탐색이 비정상적으로 진행됨
{
for(int i = 0; i < targetlevel; ++i)
{
food[i] = null;
}
food[0] = list.get(0);//search 함수 for문 일단 시작하기위해 세팅
}
static int search(int level, int targetlevel)
{
if(level == targetlevel)
{
int sour = 1;
int bitter = 0;
for(int i =0; i < level; ++i)
{
sour *= food[i].sour;
bitter += food[i].bitter;
}
return Math.abs(sour-bitter);
}
int diff = Integer.MAX_VALUE;
//이전에 테스트케이스에 선택된 재료 제외하기위해. food에서 사용된것보다 높은 id의 재료사용 예) 123, 132 는 중복이다
for(int i = food[level==0? level:level-1].ingID; i < IngredientCnt; ++i)
{
if(checked[i] == false)
{
checked[i] = true;
food[level] = list.get(i);
diff = Math.min(diff, search(level+1, targetlevel));
checked[i] = false;
}
}
return diff;
}
}