반응형
Notice
Recent Posts
Recent Comments
Link
It's easy, if you try
[SW Expert Academy] 5215:햄버거다이어트 (Java) / 부분집합 본문
반응형
import java.io.*;
import java.util.*;
public class Solution {
static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int limit =0;
static int numOfFood=0;
static int[][] foodInfo;
static boolean[] isSelected;
static Queue<int[]> queue;
static int maxNum;
public static void main(String[] args) throws Exception {
int T = Integer.parseInt(br.readLine());
for(int t=1; t<=T; t++) {
input();
maxNum = 0;
generateSubset(0);
System.out.printf("#%d %d\n", t, maxNum); // 높은 스코어 출
}
}
private static void generateSubset(int cnt) {
if(cnt == numOfFood) { // 5개를 다 돌았을 때,
int total =0;
int sumOfScore =0;
for(int i=0; i<numOfFood; i++) {
if(isSelected[i]) { // 선택 되어있으면
sumOfScore += foodInfo[i][0]; // 스코어 더함
total += foodInfo[i][1]; // 음식 칼로리 더함
if(total>limit) return; // 만약 제한 칼로리를 넘으면 그냥 return
}
}
maxNum = Math.max(maxNum, sumOfScore); // 제한 칼로리보다 낮으면서 높은 스코어를 갱신해서 저장
return;
}
isSelected[cnt] = true; // 선택
generateSubset(cnt+1);
isSelected[cnt] = false; // 비선택
generateSubset(cnt+1);
}
private static void input() throws Exception {
st = new StringTokenizer(br.readLine());
numOfFood = Integer.parseInt(st.nextToken());
limit = Integer.parseInt(st.nextToken());
foodInfo = new int[numOfFood][2];
isSelected = new boolean[numOfFood];
for(int i=0; i<numOfFood; i++) {
st = new StringTokenizer(br.readLine());
foodInfo[i][0] = Integer.parseInt(st.nextToken());
foodInfo[i][1] = Integer.parseInt(st.nextToken());
}
}
}
최초 발행 날짜: 2021-02-08
반응형
'알고리즘 > 자바(Java)' 카테고리의 다른 글
[백준/boj] 2961: 도영이가 만든 맛있는 음식 (Java) / 브루트포스 알고리즘 / 부분 집합 (3) | 2021.02.15 |
---|---|
[SW Expert Academy] 1221: GNS (JAVA) (0) | 2021.02.14 |
[백준/boj] 2206: 벽 부수고 이동하기 (Java) / BFS / 3차원 배열 (0) | 2021.02.14 |
[백준/boj] 5397: 키로거 (Java) / Deque (0) | 2021.02.12 |
[백준/boj] 13116: 30번 (Java) - 트리 / 구현 (0) | 2021.02.10 |
Comments