문제
문제
시간 제한 8초, 힙+정적 256MB 이내 혹은 스택 1MB 이내재료별 칼로리, 점수가 주어진다.
재료를 조합해 정해진 칼로리를 넘지 않되 본인이 매겨둔 재료별 점수를 모두 합쳤을 때 최대치인 값을 구하라. 같은 재료를 여러 번 사용할 수 없다.
입력
테스트 케이스의 수 T
재료의 수 N, 제한 칼로리 L (1 ≤ N ≤ 20, 1 ≤ L ≤ 10^4)
(재료의 수 N만큼 반복) 재료의 점수 T, 칼로리 K (1 ≤ T ≤ 10^3, 1 ≤ K ≤ 10^3)
출력
조합 중 가장 맛의 점수가 높은 햄버거의 점수
풀이
문제를 봤을 때 어디서 본 문제 같은데?라는 생각이 제일 먼저 들었다.
그리디인가? 싶은 생각도 잠깐 들었는데 아닌 것 같아서
일단 조합으로 먼저 풀어봤다.
import java.io.*;
import java.util.*;
public class Solution {
static int N;
static int L;
static int[][] ingredients;
static int solution(int[] picked, int current, int sum) {
int result = 0;
int temp;
if(sum > L) { // L을 초과하는 순간 끄트머리 한 자리를 빼고 전부 더해서 반환
temp = 0;
for(int i=0; i<current-1; i++) {
temp += ingredients[picked[i]][0];
}
return temp;
}
int smallest = 0; // 중복 방지하려고 최소값, 이미 고른 값 중 마지막 값 확인
if(current == 0) { // 처음 시작인 경우
smallest = -1;
} else {
smallest = picked[current-1];
}
for(int i=smallest+1; i<N; i++) {
picked[current] = i;
result = Math.max(solution(picked, current+1, sum+ingredients[i][1]), result);
}
return result;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// 칼로리 이하의 조합 중 점수가 제일 높은 것
// 같은 재료 여러 번 X
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
ingredients = new int[N][2];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
ingredients[i][0] = Integer.parseInt(st.nextToken()); // 점수
ingredients[i][1] = Integer.parseInt(st.nextToken()); // 칼로리
}
int[] arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = 0;
}
bw.write("#" + tc + " " + solution(arr, 0, 0) +"\n");
}
bw.flush();
bw.close();
br.close();
}
}깨트리고 나올 breakpoint를 정할 때, sum <= L인 경우로 정하면 모든 조합을 돌 수가 없었다. 다음 조합을 하기도 전에 return을 하기 때문에...
그래서 sum > L일 때로 정한 뒤, 마지막 한 값을 빼고 모든 점수를 더해서 출력하는 방식으로 작성해봤는데... 예제의 경우 답이 0, 1, 4의 조합이며 1000을 넘지 않는 칼로리를 가진 햄버거이다...
그래서 최대 칼로리인 L을 넘지 않는데도 출력을 하자면... L을 넘지 않거나 같으며 방금 전에 뽑은 값이 == N-1인 값도 전부 출력하게 변경해보면
import java.io.*;
import java.util.*;
public class Solution {
static int N;
static int L;
static int[][] ingredients;
static int solution(int[] picked, int current, int sum) {
int result = 0;
int temp;
if(sum > L) { // L을 초과하는 순간 끄트머리 한 자리를 빼고 전부 더해서 반환
temp = 0;
for(int i=0; i<current-1; i++) {
System.out.print(picked[i] + " ");
temp += ingredients[picked[i]][0];
}
return temp;
}
int smallest = 0; // 중복 방지하려고 최소값, 이미 고른 값 중 마지막 값 확인
if(current == 0) { // 처음 시작인 경우
smallest = -1;
} else {
smallest = picked[current-1];
}
if(smallest == N-1) { // 새로 추가된 if문!!!
temp = 0;
for(int i=0; i<current; i++) {
temp += ingredients[picked[i]][0];
}
return temp;
}
for(int i=smallest+1; i<N; i++) {
picked[current] = i;
result = Math.max(solution(picked, current+1, sum+ingredients[i][1]), result);
}
return result;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
ingredients = new int[N][2];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
ingredients[i][0] = Integer.parseInt(st.nextToken()); // 점수
ingredients[i][1] = Integer.parseInt(st.nextToken()); // 칼로리
}
int[] arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = 0;
}
bw.write("#" + tc + " " + solution(arr, 0, 0) +"\n");
}
bw.flush();
bw.close();
br.close();
}
}약간 긴가민가했는데 통과는 했다.
문제를 풀며
조합을 응용해서 풀었는데 작성된 코드를 다시 보니 DFS + 백트래킹 같기도 하고?... 메모이제이션을 적용하면 더 개선할 수 있을 것 같다.
근데... 조건도 덕지덕지 붙여야 하고 (N=20일 때 100만 회 연산으로 실행됨, 사실상 모든 N-1이 들어간 조합은 다 검색해보는 것이므로, 만약 입력되는 수의 개수가 더 커졌더라면 시간 초과가 났을 것) 내가 생각하던 것처럼 깔끔하게 작동하게 풀지 못한 것 같아 다른 분들의 풀이를 찾아보았다.
어디서 봤나 했더니 가방 문제였다!!! 왜 기억을 못 했지... 가방에 가치 최대로 짐 싸던 그 문제랑 완전히 똑같았다. 이 문제는 대표적으로 DFS, DP으로 해결할 수 있는 문제였다. 하나씩 정리해보자면 다음과 같다.
재귀를 사용
탈출 케이스 : count ≥ N && 칼로리 합계 ≤ L max 값 갱신하여 return
현재 index(=count)를 선택하는 경우와 선택하지 않는 경우로 나누어 DFS 진행 (내 풀이와 비슷)
DP[N+1][L+1] = N개 이하의 재료를 사용해 L 이하의 칼로리로 얻을 수 있는 최대 점수
for(int i=1;i<=N;i++) { for(int j=0;j<=L;j++) { if(j < ingredients[i-1][1]) { // 만약 현재 재료의 칼로리보다 j가 작은 경우 dp[i][j] = dp[i-1][j]; } else { dp[i][j] = Math.max(dp[i-1][j], // 선택 X dp[i-1][j-ingredients[i-1][1]] + ingredients[i-1][0]; // 선택 O } }만약 현재 재료의 칼로리보다 j(현재 기준점으로 삼은 칼로리)가 더 작으면 = N개의 재료로 선택할 수 없다. ⇒ 이전 값을 그대로 들고 와서 저장
아닌 경우(현재 재료를 넣어도 되는 경우) dp[i-1][j]와 dp[i-1][j-현 재료의 칼로리] + 현 재료의 점수를 비교해 더 큰 값을 집어넣는다. ⇒ 값 갱신
가방 문제라는 걸 깨달았어도 점화식을 금방 떠올릴 수 있었을까 싶다. 표를 그려보는 연습을 해야겠다...