[BOJ 7579] 앱 (Java)

BOJ 7579 앱

난이도 : 골드 3

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

7579번: 앱

 

전략

냅색 문제랑 비슷한 유형이라서 우선 메모리 크기를 살펴본다.

m_i 는 최대 10,000,000인 정수이며 N이 최대 100이므로 메모리 크기에 대해 dp 배열을 생성하면

GB 단위의 메모리를 사용하게 되므로 불가능하다.

 

c_i 는 최대 100이므로 교체 비용을 기준으로 dp를 진행해야 한다.

dp를 2차원 배열로 표현하여 [1, i] 범위의 앱까지 탐색했을 때 j 만큼의 비용으로 얻을 수 있는 최대 메모리를 갱신한다.

 

이 때 dp[i][j]가 M 이상이고 현재 기록된 값보다 작은 비용이면 결과를 갱신한다. 

 

시행착오

dp[i][j] = dp[i - 1][j] 를 먼저 적용하는 것을 빼먹었다.

앞으로는 이런 실수하지 않도록 주의해야될 것 같다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M;
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);

        int[] memory = new int[N + 1];
        int[] cost = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            memory[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            cost[i] = Integer.parseInt(st.nextToken());

        int[][] dp = new int[N + 1][100 * N + 1];
        int ans = Integer.MAX_VALUE;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - cost[i] >= 0)
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost[i]] + memory[i]);
                if (dp[i][j] >= M)
                    ans = Math.min(ans, j);
            }
        }
        System.out.println(ans);
        br.close();
    }
}

 

깨달은 점

DP가 아직 너무 어려운 것 같다. 많은 문제를 풀어보면서 연습해야할 것 같다.