https://www.algospot.com/judge/problem/read/SUSHI
algospot.com :: SUSHI
회전초밥 문제 정보 문제 문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의
www.algospot.com
코드 설명 및 코드
재귀와 메모이제이션을 활용할 경우입니다.
이 코드의 경우, 1e9 + 1, 10억+1 의 개수는 메모리 초과가 나오기 때문에, 재귀함수 + 메모이제이션 조합으로 배낭문제를 해결할 수 없습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, C, T, K;
private static int answer = 0;
private static int[] price, pref;
private static int[] cache = new int[(int) 1e9 + 1];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
price = new int[N];
pref = new int[N];
Arrays.fill(cache, -1);
for(int i=0;i<N; i++) {
price[i] = Integer.parseInt(st.nextToken());
}
System.out.println(sushi(M));
}
}
// budget 만큼의 예산으로 초밥을 먹어서 얻을 수 있는 최대 선호도
private static int sushi(int budget) {
// 메모이제이션
if (cache[budget] != -1) return cache[budget];
int ret = 0;
for (int dish = 0; dish < N; dish++) {
if (budget < price[dish]) continue;
ret = Math.max(ret, sushi(budget - price[dish]) + pref[dish]);
}
return cache[budget] = ret;
}
}
반복적 동적계획법을 적용합니다. 여전히 M이 최대값이 들어올경우 처리하지 못합니다. 메모리초과가 발생합니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, C, T, K;
private static int answer = 0;
private static int[] price, pref;
private static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
price = new int[N];
pref = new int[N];
cache = new int[M+1];
Arrays.fill(cache, -1);
for(int i=0;i<N; i++) {
st = new StringTokenizer(br.readLine());
price[i] = Integer.parseInt(st.nextToken());
pref[i] = Integer.parseInt(st.nextToken());
}
System.out.println(sushi2());
}
}
public static int sushi2() {
int ret = 0;
cache[0] = 0; //예산이 0 원일떄는 선호도의 합은 0입니다. 처음에 -1 로 초기화해서 1이 감소된 값이 나왔었습니다.
for (int budget = 1; budget <= M; budget++) {
cache[budget] = 0;
for (int dish = 0; dish < N; dish++) {
if (budget >= price[dish]) {
cache[budget] = Math.max(cache[budget], cache[budget - price[dish]] + pref[dish]);
}
}
ret = Math.max(ret, cache[budget]);
}
return ret;
}
// budget 만큼의 예산으로 초밥을 먹어서 얻을 수 있는 최대 선호도
private static int sushi(int budget) {
// 메모이제이션
if (cache[budget] != -1) return cache[budget];
int ret = 0;
for (int dish = 0; dish < N; dish++) {
if (budget < price[dish]) continue;
ret = Math.max(ret, sushi(budget - price[dish]) + pref[dish]);
}
return cache[budget] = ret;
}
}
메모리초과를 없애주기 위해 각 초밥의 가격이 최대 2만원이기 떄문에, cache[budget] 이후를 구하는데 cache[budget - 20000] 전의 원소들은 필요 없습니다. 이유는, 다른 초밥을 구매했을떄 지금까지 예산으로 구매한 초밥의 최대 선호도를 통해 현재 budget의 최대 선호도를 구하는데, 이때 초밥의 가격이 2만원이기에 우리가 필요한 이전 초밥 Index위치만 구하면 됩니다. 그러므로 budget % 20001 을 통해 계산할 수 있습니다. 슬라이딩 윈도우 기법을 적용하여 메모리를 줄입니다.
이를 통해 메모리초과를 벗어날 수 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, C, T, K;
private static int answer = 0;
private static int[] price, pref;
private static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
price = new int[N];
pref = new int[N];
cache = new int[20001];
Arrays.fill(cache, -1);
for(int i=0;i<N; i++) {
st = new StringTokenizer(br.readLine());
price[i] = Integer.parseInt(st.nextToken());
pref[i] = Integer.parseInt(st.nextToken());
}
System.out.println(sushi2());
}
}
public static int sushi2() {
int ret = 0;
cache[0] = 0; //예산이 0 원일떄는 선호도의 합은 0입니다. 처음에 -1 로 초기화해서 1이 감소된 값이 나왔었습니다.
for (int budget = 1; budget <= M; budget++) {
cache[ budget % 20001] = 0;
for (int dish = 0; dish < N; dish++) {
if (budget >= price[dish]) {
cache[budget % 20001] = Math.max(cache[budget % 20001], cache[(budget - price[dish]) % 20001] + pref[dish]);
}
}
ret = Math.max(ret, cache[budget % 20001]);
}
return ret;
}
// budget 만큼의 예산으로 초밥을 먹어서 얻을 수 있는 최대 선호도
private static int sushi(int budget) {
// 메모이제이션
if (cache[budget] != -1) return cache[budget];
int ret = 0;
for (int dish = 0; dish < N; dish++) {
if (budget < price[dish]) continue;
ret = Math.max(ret, sushi(budget - price[dish]) + pref[dish]);
}
return cache[budget] = ret;
}
}
시간복잡도는 O(nm)이기에 여전히 m이 10억개, m이 2*10^5 가 들어오면 시간초과가 발생합니다.
m의 크기를 줄여줘야하는데, 이떄 예산, 초밥의 최소 가격이 100원 단위이므로 100씩 나눠줍니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static int N, M, C, T, K;
private static int answer = 0;
private static int[] price, pref;
private static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken()) / 100;
price = new int[N];
pref = new int[N];
cache = new int[201];
Arrays.fill(cache, -1);
for(int i=0;i<N; i++) {
st = new StringTokenizer(br.readLine());
price[i] = Integer.parseInt(st.nextToken()) / 100;
pref[i] = Integer.parseInt(st.nextToken());
}
System.out.println(sushi2());
}
}
public static int sushi2() {
int ret = 0;
cache[0] = 0; //예산이 0 원일떄는 선호도의 합은 0입니다. 처음에 -1 로 초기화해서 1이 감소된 값이 나왔었습니다.
for (int budget = 1; budget <= M; budget++) {
cache[ budget % 201] = 0;
for (int dish = 0; dish < N; dish++) {
if (budget >= price[dish]) {
cache[budget % 201] = Math.max(cache[budget % 201], cache[(budget - price[dish]) % 201] + pref[dish]);
}
}
ret = Math.max(ret, cache[budget % 201]);
}
return ret;
}
// budget 만큼의 예산으로 초밥을 먹어서 얻을 수 있는 최대 선호도
private static int sushi(int budget) {
// 메모이제이션
if (cache[budget] != -1) return cache[budget];
int ret = 0;
for (int dish = 0; dish < N; dish++) {
if (budget < price[dish]) continue;
ret = Math.max(ret, sushi(budget - price[dish]) + pref[dish]);
}
return cache[budget] = ret;
}
}