문제 이해

식재료 N개가 주어지고, 영양분과 가격이 주어질 것이다.
또한, 최소한으로 충족되어야 할 영양분들의 값들이 주어질 것이다.

이 때, 주어진 영양분 값을 모두 충족시키면서(값 이상으로 만들면서) 비용이 최소가 되는 선택을 하고 싶다.
최소 비용과 이 때 선택되는 (오름차순으로) 식재료 번호 List를 출력하는 문제이다.
최소 비용으로 만드는 경우가 2개 이상 존재한다면, 식재료 번호가 사전 순으로 가장 앞에 있는 식재료 List를 출력한다.
답이 없을 경우 -1을 출력한다.

문제 풀이

이 문제를 보고 Brute Force로 푸는 방법밖에 생각나지 않았다.
그렇다면 Brute Force를 어떻게 그나마 효율적으로 수행할지 생각했다.

내가 생각한 방법은 재귀함수를 활용하는 방식이다.
(1,2) 식재료를 뽑든, (2,1) 식재료를 뽑든 영양분의 합과 가격은 동일하다.
따라서, 나는 N번째 식재료를 뽑았을 때, (N+1) ~ 마지막 식재료를 뽑았을 때의 경우를 재귀함수를 통해 고려하도록 만들었다.
또한 재귀함수의 종료 조건을 주어진 식재료 번호를 넘어서거나, 주어진 영양분의 합을 충족시키면 바로 재귀함수가 종료되도록 만들었다.
(어차피 "최소 비용"을 구하는 것이므로, 조건을 충족시키면 더 이상 식재료 추가할 필요 없음)

코드

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

class Food implements Comparable<Food> {
	int protein;
	int fat;
	int rice;
	int vitamin;
	int money;
	int num;
	
	public Food(int protein, int  fat, int rice, int  vitamin, 
    			int money, int num) {
		this.protein = protein;
		this.fat = fat;
		this.rice = rice;
		this.vitamin = vitamin;
		this.money = money;
		this.num = num;
	}
	
	
	public Food add(Food A) {
		return new Food(A.protein + this.protein, A.fat + this.fat, 
        				A.rice + this.rice, A.vitamin + this.vitamin, 
                        A.money+this.money, num);
	}

	@Override
	public int compareTo(Food f) {
		return f.protein - this.protein;
	}

}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static ArrayList<Food> foods;
	static int N;
	static int protein, fat, rice, vitamin;
	
	static int min = Integer.MAX_VALUE; // 최소 금액 저장 공간
	static ArrayList<Integer> answer;
	
	
	static void rec(Food f, int i, ArrayList<Integer> list) {
		if(i>=N) return;
        // 준비된 식재료 번호를 넘어가므로 재귀함수 종료
		
		list.add(i);
        // 리스트에 현재 식재료 번호 추가시킴
		
		if(f.protein >= protein && f.fat >= fat 
           && f.rice >= rice && f.vitamin >= vitamin) {
           // 영양분 합 조건을 만족시킴. 따라서 재귀함수를 종료시켜야 함

			if(min > f.money) {
                // 최소 금액보다 현재 금액이 작으므로 Update
				min = f.money;
				answer = new ArrayList(list);
			}
			else if(min == f.money) {
                // 최소 금액 = 현재 금액
                // 사전순으로 빠른 경우로 Update 해야하므로,
                // compareTo()로 String끼리 비교하는 로직 추가
				String str = list.toString();
				if(answer.toString().compareTo(str) > 0) {
					answer = new ArrayList(list);
				}
			}
			return;
		}
		
		for(int j = i+1;j<N;j++) {
			rec(f.add(foods.get(j)),j,list);
            // (i+1) ~ (N-1)번째 식재료를 넣어서 다시 재귀함수를 돌림
			list.remove(list.size()-1);
            // 재귀함수가 종료되면, 마지막에 추가된(다음 재귀함수에서 추가된)
            // 식재료를 list에서 제거해야 하므로 수행하는 명령
		}
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		
		foods = new ArrayList<Food>();
		
		protein = sc.nextInt();
		fat = sc.nextInt();
		rice = sc.nextInt();
		vitamin = sc.nextInt();
		
		for(int i =0;i<N;i++) {
			foods.add(new Food(sc.nextInt(), sc.nextInt(), sc.nextInt(), 
            					sc.nextInt(),sc.nextInt(),i));
		}
		
		for(int i =0;i<N;i++) {
			rec(foods.get(i), i, new ArrayList<>());
		}
		
		if(min==Integer.MAX_VALUE) {
            // 조건을 만족시키는 경우가 없는 Case
			System.out.println(-1);
			return;
		}
        
		System.out.println(min);
		
		for(int s:answer) {
			System.out.print(s+1+" ");
		}
	}
    
	static class FastReader // 빠른 입력을 위한 클래스
}

결과

• 두번째 런타임 에러 : 조건을 만족시키지 않는 경우도 존재한다는 것을 고려하지 않아 NullPointer Exception이 발생했다