이번에 풀어본 문제는
백준 19942번 다이어트 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int [][] map;
static int [] values;
static int min = Integer.MAX_VALUE;
static HashMap<Integer,ArrayList<String>> hm;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
values = new int[4];
int valuesIdx = 0;
while(st.hasMoreTokens())
{
values[valuesIdx++] = Integer.parseInt(st.nextToken());
}
map = new int[n+1][5];
hm = new HashMap<>();
for(int i = 1; i <= n; ++i)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j < 5; ++j)
{
map[i][j] = Integer.parseInt(st.nextToken());
}
}
StringBuilder sb;
for(int i = 1; i < 1 << n; ++i)
{
sb = new StringBuilder();
for(int j = 0; j < n; ++j)
{
if((i & 1 << j) > 0)
{
sb.append(j+1+" ");
}
}
sum(sb.toString());
}
if(hm.isEmpty())
{
System.out.print("-1");
return;
}
for(Integer key : hm.keySet())
{
if(key == min)
{
ArrayList<String> tmpAl = hm.get(key);
Collections.sort(tmpAl);
System.out.printf("%d\n%s",key,tmpAl.get(0));
break;
}
}
}
static void sum(String selections)
{
StringTokenizer st = new StringTokenizer(selections);
int [] curVal = new int[5];
int idx = 0;
while(st.hasMoreTokens())
{
int cur = Integer.parseInt(st.nextToken());
idx = 0;
for(int v : map[cur])
{
curVal[idx++] += v;
}
}
int price = isOK(curVal);
if(price == -1) return;
hm.putIfAbsent(price,new ArrayList<>());
ArrayList<String> tmp = hm.get(price);
tmp.add(selections);
hm.put(price,tmp);
if(price < min) min = price;
}
static int isOK(int [] getArr)
{
for(int i = 0; i < values.length; ++i)
{
if(getArr[i] < values[i]) return -1;
}
return getArr[4];
}
}
완전탐색 문제입니다.
비트마스킹을 통해 모든 경우의 수를 구해 해당 인덱스를 탐색하여 sum함수로 보내줍니다. String형태로 넘어온 경우의 수를 각 인덱스 별로 분류하여 해당되는 영양소들의 누적합을 구해줍니다. 마지막으로 isOK함수에서 적합성을 판별한 후 해당되는 조건에 만족하는 경우의 수라면 비용과 만들어진 조합을 hashmap에 담아줍니다.
모든 탐색을 마친 후, 최소 가격을 key값으로 할때의 ArrayList를 정렬하여 사전 순으로 가장 빠른 조합을 출력해주면 해결됩니다.
비트마스킹을 훈련해보고 싶어서 풀어보았습니다.
평소 순열, 조합이 조금 헷갈렸어서 해당 문제들을 새로운 방식으로도 접근할 수 있도록 다양하게 연습해 볼 생각입니다.