백준 7579 앱 Java [DP, 배낭문제]

https://www.acmicpc.net/problem/7579

7579번: 앱

 

 

바이트를 확보하라는 문제라서 바이트를 가지고 dp를 만들어볼까 했는데 범위가 10,000,000까지라서

100 x 10,000,000 시간복잡도도 문제인데 공간복잡도도 문제가 생길 정도로 크다 (int 기준 약 4GB)

그래서 비용을 이용하여 dp로 풀기로했다

범위가 100까지라서 100 x 100 1만이면 여유있게 풀 수 있다

 

바이트와 비용을 입력 받은 후 반복문으로

비용이 0이면 무조건 종료시키고 확보해야하는 바이트에서 뺀다

비용을 기준으로 끝에서부터 1씩 줄여가면서 dp배열에 0이 아닌 값(x)이 저장되어 있으면

현재 인덱스 + 비용의 dp배열 값(y)을 비교하여 x + 바이트 와 y 중 더 큰 값으로  갱신한다

그리고 dp배열의 비용 인덱스 값을 바이트와 비교해서 더 큰 값으로 갱신한다

 

import java.io.*;
import java.util.*;

public class Main {
    static final int MAX_MEMORY = 10001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        StringTokenizer bites = new StringTokenizer(br.readLine());
        StringTokenizer costs = new StringTokenizer(br.readLine());
        int[] dp = new int[MAX_MEMORY];
        int index = 0;
        for (int n = 0; n < N; n++) {
            int bite = Integer.parseInt(bites.nextToken());
            int cost = Integer.parseInt(costs.nextToken());
            if (cost == 0) {
                M -= bite;
                continue;
            }
            for (int i = index; i > 0; i--) {
                if (dp[i] != 0) dp[i + cost] = Math.max(dp[i + cost], dp[i] + bite);
            }
            dp[cost] = Math.max(dp[cost], bite);
            index += cost;
        }
        for (int i = 0; i < MAX_MEMORY; i++) {
            if (dp[i] >= M) {
                System.out.println(i);
                break;
            }
        }
    }
}

추가적으로 index라는 변수는 cost가 저장된 최대 인덱스로,

10000번째부터 계속 체크하는 것보다 시간 절약할 수 있을 것 같아 넣었다

처음풀이할 때는 dp배열을 2개만들어서 교체하는 방식을 사용했는데

어차피 뒤에서부터 찾아서 갱신하기 때문에 1개만 만들어도 충분했다

그리고 bites와 costs를 stream으로 배열로 만들어서 사용했었는데

배열을 사용하지 않고 StringTokenizer로 하나씩 잘라서 사용하여 메모리를 덜 사용할 것을 기대했지만 아니었다...