Development Palette
s5215_햄버거다이어트 본문
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
0/1 Knapsack 문제를 그대로 적용할 수 있는 조합 문제!
저번에 그냥 조합으로 풀었을 때 1개의 케이스만 맞고 실패했었는데 드디어 풀었다,,
package com.DP.s5215_햄버거다이어트;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 0/1Knapsack 으로 풀 수 있는 문제
//민기의 햄버거 재료에 대한 점수와 가게에서 제공하는 재료에 대한 칼로리가 주어졌을 때,
// 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합
//햄버거의 선호도는 조합된 재료들의 맛에 대한 점수의 합으로 결정되고, 같은 재료를 여러 번 사용할 수 없으며, 제한된 칼로리만 사용 가능
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 음식 개수
int L = Integer.parseInt(st.nextToken()); // 제한된 칼로리
// 음식을 index로 구분하고 점수와 칼로리 저장
int [] score = new int[N+1];
int [] kcal = new int[N+1];
for (int n = 1; n <= N; n++) {
st = new StringTokenizer(br.readLine());
score[n] = Integer.parseInt(st.nextToken());
kcal[n] = Integer.parseInt(st.nextToken());
}
int [][] burger = new int[N+1][L+1];
for (int n = 1; n <= N ; n++) {
for (int l = 1; l <= L; l++) {
if(kcal[n] <= l){ // 해당 음식이 남은 칼로리 이내일 때
burger[n][l] = Math.max(burger[n-1][l],score[n]+burger[n-1][l-kcal[n]]);
}else{
burger[n][l] = burger[n-1][l];
}
}
}
System.out.println("#"+t+" "+burger[N][L]);
}
br.close();
}
}
/*
1
5 1000
100 200
300 500
250 300
500 1000
400 400
*/ //750
'Algorithm > SWEA' 카테고리의 다른 글
6026_성수의비밀번호공격 (0) | 2021.09.28 |
---|---|
n7465_창용 마을 무리의 개수 (0) | 2021.08.24 |
n3289_서로소 (0) | 2021.08.24 |
[D4] n1223_계산기2 (0) | 2021.08.20 |
[D3] n6808_규영이와인영이의카드게임 (0) | 2021.08.14 |
Comments