[백준] 19942 다이어트 - 브루트포스(BruteForce) + 백트래킹(BackTracking) JAVA

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

19942번: 다이어트

코드설명

브루트포스(BruteForce) + 백트래킹(BackTracking) 문제입니다.

 

문제에서 유의해야할점은 사전순으로 출력하는 점입니다.

3
0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
https://www.acmicpc.net/board/view/69007
 
정답 
0
1 2 3
 
내 출력:
0
3
 
 
 
1 0 0 
tempC:0
2 0 0 
tempC:0
3 0 0 
tempC:0
1 2 0 
tempC:0
1 3 0 
tempC:0
2 3 0 
tempC:0
1 2 3 
tempC:0

사전순이라는 말을 제대로 고려하지않았습니다.

3 과 1 2 3 중에 사전순으로 더 앞서는것은 1 2 3 입니다. 그렇기에 3 이 아닌 1 2 3 을 출력합니다.

 

사전순으로 어떻게 출력해야하는 고민이 생겼었습니다.

public static ArrayList<String> answerArr = new ArrayList<String>();
 
 
...
 
 
 
if(tempP >= minimumE.mp && tempF >= minimumE.mf && tempS >= minimumE.ms && tempV >= minimumE.mv) {
    if(answerCost > tempC) {
        answerArr.clear();
        answerCost = tempC;
        String str = "";
        for(int i=0;i<level;i++) {
            str += output[i]+" ";
        }
        answerArr.add(str);
    }
    else if(answerCost == tempC) {
        String str = "";
        for(int i=0;i<level;i++) {
            str += output[i]+" ";
        }
        answerArr.add(str);
    }
}
 
 
...
 
 
Collections.sort(answerArr);
System.out.println(answerCost);
System.out.println(answerArr.get(0));

위와 같이 ArrayList<String>을 선언하여 String을 사전순으로 정렬합니다.

이떄, 처음에 answerArr.add(output[i]) 이런식으로해서 오류가 있었습니다.

answerCost보다 작으면 answerArr을 초기화하고 새로운 값을 넣어주고,

answerCost와 같으면 같은값일떄는 사전순으로 초기화하니 answerArr에 계속값을 넣어주고 이후에 Collections.sort로 사전순 정렬합니다.

 

 

코드

객체지향적으로 짜본 정답 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M, K;
	public static int MAXVALUE = 15 * 500 + 1;
	public static int answer = MAXVALUE;
	public static boolean[] visited;
	public static StringBuilder sb = new StringBuilder();
	public static Nutrition[] GNutrition;
	public static Nutrition standardNutrition;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int mp = Integer.parseInt(st.nextToken());
		int mf = Integer.parseInt(st.nextToken());
		int ms = Integer.parseInt(st.nextToken());
		int mv = Integer.parseInt(st.nextToken());
		standardNutrition = new Nutrition(mp, mf, ms, mv, 0);
		
		GNutrition = new Nutrition[N];
		visited = new boolean[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			GNutrition[i] = new Nutrition(a, b, c, d, e);
		}
		
		simulate(0, new Nutrition(0, 0, 0, 0, 0));
		
		if(answer == MAXVALUE) {
			System.out.println(-1);
		}else {
			System.out.println(answer);
		}
		System.out.println(sb.toString());
	}
	
	public static void simulate(int level, Nutrition nutrition) {
		
		//만약 영양분의 각각 합이 통과라면, 최소 비용인지 비교하여 저장한다.
		if(nutrition.overEnergyCheck(standardNutrition) == true) {
			if(nutrition.price < answer) {
				answer = nutrition.price;
				sb = new StringBuilder();
				for(int i=0;i<N;i++) {
					if(visited[i] == true) {
						sb.append((i+1)+" ");
					}
				}
			}
		}
		
		if(level == N) {
			
			return ;
		}
		
		//선택하는경우
		visited[level] = true;
		Nutrition nutriTemp = GNutrition[level];
		simulate(level + 1, nutrition.returnNewNutrition(nutriTemp));
		visited[level] = false;
		
		//선택하지 않는 경우
		simulate(level + 1, nutrition);
		
	}
	
	
}
 
class Nutrition{
	int protein;
	int jibang;
	int tansu;
	int vitamin;
	int price;
	
	public Nutrition(int protein, int jibang, int tansu, int vitamin, int price) {
		this.protein = protein;
		this.jibang = jibang;
		this.tansu = tansu;
		this.vitamin = vitamin;
		this.price = price;
	}
	
	public Nutrition returnNewNutrition(Nutrition temp) {
		
		int protein = this.protein + temp.protein;
		int jibang = this.jibang + temp.jibang;
		int tansu = this.tansu + temp.tansu;
		int vitamin = this.vitamin + temp.vitamin;
		int price = this.price + temp.price;
		
		return new Nutrition(protein, jibang, tansu, vitamin, price);
	}
	
	
	public boolean overEnergyCheck(Nutrition standardNutrition) {
		if(this.protein >= standardNutrition.protein && this.jibang >= standardNutrition.jibang && this.tansu >= standardNutrition.tansu && this.vitamin >= standardNutrition.vitamin ) {
			return true;
		}
		
		return false;
	}
}

 

정답코드(사전순 고려)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	public static int N;
	public static int[] arr;
	public static int[] output;
	public static int targetN;
	public static boolean[] visited;
	public static ArrayList<String> answerArr = new ArrayList<String>();
	public static ArrayList<Integer> compareArr = new ArrayList<Integer>();
	public static int answerCost = Integer.MAX_VALUE;
	public static Node minimumE;
	public static NodeCost[] nodeArr;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	nodeArr = new NodeCost[N];
    	
    	st = new StringTokenizer(br.readLine());
    	int mp = Integer.parseInt(st.nextToken());
    	int mf = Integer.parseInt(st.nextToken());
    	int ms = Integer.parseInt(st.nextToken());
    	int mv = Integer.parseInt(st.nextToken());
    	minimumE = new Node(mp, mf, ms, mv);
    	
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int p = Integer.parseInt(st.nextToken());
        	int f = Integer.parseInt(st.nextToken());
        	int s = Integer.parseInt(st.nextToken());
        	int v = Integer.parseInt(st.nextToken());
        	int c = Integer.parseInt(st.nextToken());
        	nodeArr[i] = new NodeCost(p, f, s, v, c);
    	}
    	
    	for(int cnt=1;cnt<=N;cnt++) { //이루어진 비타민이 1개일떄, 2개일떄 ... 모두 구합니다.
    		targetN = cnt;
    		output = new int[N];
    		visited = new boolean[N];
    		simulate(0, 1);
    	}
    	if(answerCost == Integer.MAX_VALUE) {
    		System.out.println("-1");
    		return ;
    	}
    	Collections.sort(answerArr);
    	System.out.println(answerCost);
    	System.out.println(answerArr.get(0));
    	
    	
    }
	
	//1 2 3 
	//1 2 4
	//1 2 5
	//1 2 6
	//1 3 4 .............
	public static void simulate( int level, int idx) {
		if(level == targetN) {
			int tempP =0;
			int tempF =0;
			int tempS =0;
			int tempV =0;
			int tempC =0;
			for(int i=0;i<level;i++) {
				tempP += nodeArr[output[i]-1].p;
				tempF += nodeArr[output[i]-1].f;
				tempS += nodeArr[output[i]-1].s;
				tempV += nodeArr[output[i]-1].v;
				tempC += nodeArr[output[i]-1].c;
			}
			
			if(tempP >= minimumE.mp && tempF >= minimumE.mf && tempS >= minimumE.ms && tempV >= minimumE.mv) {
				if(answerCost > tempC) {
					answerArr.clear();
					answerCost = tempC;
					String str = "";
					for(int i=0;i<level;i++) {
						str += output[i]+" ";
					}
					answerArr.add(str);
				}
				else if(answerCost == tempC) {
					String str = "";
					for(int i=0;i<level;i++) {
						str += output[i]+" ";
					}
					answerArr.add(str);
				}
 
			}
			
			return ;
		}
		for(int i=idx;i<=N;i++) {
			output[level] = i;
			simulate(level + 1, i + 1);
			output[level] = -1;
		}
	}
	
}
class NodeCost{
	int p;
	int f;
	int s;
	int v;
	int c;
	public NodeCost(int p, int f, int s, int v, int c) {
		this.p = p;
		this.f = f;
		this.s = s;
		this.v = v;
		this.c=c;
	}
}
 
class Node{
	int mp;
	int mf;
	int ms;
	int mv;
	public Node(int mp, int mf, int ms, int mv) {
		this.mp = mp;
		this.mf = mf;
		this.ms = ms;
		this.mv = mv;
	}
}

 

 

사전순고려하지않은코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	public static int N;
	public static int[] arr;
	public static int[] output;
	public static int targetN;
	public static boolean[] visited;
	public static ArrayList<Integer> answerArr = new ArrayList<Integer>();
	public static int answerCost = Integer.MAX_VALUE;
	public static Node minimumE;
	public static NodeCost[] nodeArr;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	nodeArr = new NodeCost[N];
    	
    	st = new StringTokenizer(br.readLine());
    	int mp = Integer.parseInt(st.nextToken());
    	int mf = Integer.parseInt(st.nextToken());
    	int ms = Integer.parseInt(st.nextToken());
    	int mv = Integer.parseInt(st.nextToken());
    	minimumE = new Node(mp, mf, ms, mv);
    	
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int p = Integer.parseInt(st.nextToken());
        	int f = Integer.parseInt(st.nextToken());
        	int s = Integer.parseInt(st.nextToken());
        	int v = Integer.parseInt(st.nextToken());
        	int c = Integer.parseInt(st.nextToken());
        	nodeArr[i] = new NodeCost(p, f, s, v, c);
    	}
    	
    	for(int cnt=1;cnt<=N;cnt++) { //이루어진 비타민이 1개일떄, 2개일떄 ... 모두 구합니다.
    		targetN = cnt;
    		output = new int[N];
    		visited = new boolean[N];
    		simulate(0, 1);
    	}
    	if(answerCost == Integer.MAX_VALUE) {
    		System.out.println("-1");
    		return ;
    	}
    	System.out.println(answerCost);
    	for(int a : answerArr) {
    		System.out.print(a + " ");
    	}
    	
    	
    }
	
	//1 2 3 
	//1 2 4
	//1 2 5
	//1 2 6
	//1 3 4 .............
	public static void simulate( int level, int idx) {
		if(level == targetN) {
			for(int out:output) {
				System.out.print(out+" ");
			}
			System.out.println();
			int tempP =0;
			int tempF =0;
			int tempS =0;
			int tempV =0;
			int tempC =0;
			for(int i=0;i<level;i++) {
				tempP += nodeArr[output[i]-1].p;
				tempF += nodeArr[output[i]-1].f;
				tempS += nodeArr[output[i]-1].s;
				tempV += nodeArr[output[i]-1].v;
				tempC += nodeArr[output[i]-1].c;
			}
			System.out.println("tempC:"+tempC);
			
			if(tempP >= minimumE.mp && tempF >= minimumE.mf && tempS >= minimumE.ms && tempV >= minimumE.mv) {
				if(answerCost > tempC) {
					answerArr.clear();
					answerCost = tempC;
					for(int i=0;i<level;i++) {
						answerArr.add(output[i]);
					}
				}
			}
			
			return ;
		}
		for(int i=idx;i<=N;i++) {
			output[level] = i;
			simulate(level + 1, i + 1);
			output[level] = -1;
		}
	}
	
}
class NodeCost{
	int p;
	int f;
	int s;
	int v;
	int c;
	public NodeCost(int p, int f, int s, int v, int c) {
		this.p = p;
		this.f = f;
		this.s = s;
		this.v = v;
		this.c=c;
	}
}
 
class Node{
	int mp;
	int mf;
	int ms;
	int mv;
	public Node(int mp, int mf, int ms, int mv) {
		this.mp = mp;
		this.mf = mf;
		this.ms = ms;
		this.mv = mv;
	}
}