문제
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
풀이
부분집합을 구하는 것과 비슷한 문제였다.
재료는 포함될 수도 있고 안될 수도 있다.
따라서 부분집합을 구하듯이 재료들의 부분집합들을 구해 맛에 대한 점수를 구하면 될것이다.
1. 재료들을 고를 수 있는 모든 부분집합을 고른다.
2. 매개변수를 이용하여 함수에서 맛 점수 합과 칼로리 합을 가지고 다니며 확인한다.
3-1. 칼로리 합이 제한된 칼로리보다 높으면 return
3-2. 부분집합을 완성했으면(n개의 재료들에 대해 포함되는지 모두 확인했을때) 맛 점수를 갱신(최대값으로)
코드
import java.io.*;
import java.util.*;
class Solution {
static int n, l;
static int taste[];
static int calorie[];
static int max;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for(int test = 1; test <= T; test++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
taste = new int [n];
calorie = new int [n];
visited = new boolean [n];
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
taste[i] = t;
calorie[i] = k;
}
max = 0;
back(0, 0, 0);
System.out.println("#"+test+" "+max);
}
}
static void back(int idx, int sum, int cal) {
if(cal > l) {
return;
}
if(idx == n) {
if(sum > max)
max = sum;
return;
}
back(idx+1, sum + taste[idx], cal + calorie[idx]);
back(idx+1, sum, cal);
}
}