[백준 7579] 앱 / 자바 / dp(기초)

#문제         

레벨: G4
알고리즘: dp(기초)
풀이시간: 1시간
힌트 참조 유무: 유

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

 

---

#문제 풀이        

dp에 담기는 것은 i의 비용으로 비활성화하는 앱들의 비용 합계를 나타낸다.

M으로 dp배열을 만들면 메모리 초과가 날 것을 직관적으로 알 수 있다. dp 배열을 cost로 잡는다. 이 dp는 이차원배열 풀이와 일차원 배열 풀이가 있다.

이차원 배열 풀이

dp[i][j] 에서 i는 1~i 앱까지 탐색했는지 나타내고 j는 cost를 나타낸다. 즉, dp 배열은 1 ~ i번까지 탐색하여 cost j를 이용하여 최대한 비울 수 있는 메모리를 나타낸다.

 

일차원 배열 풀이

dp[i]에서 i는 i의 cost가 주어졌을 때 최대한 비울 수 있는 메모리를 나타낸다. 왼쪽에서 오른쪽 순으로 빨간색 화살표와 같이 배열 값을 업데이트 하고 파란색 동그라미에서일 때 정답을 찾아낸다.

---

#풀이 코드      

[dp 이차원 배열]

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int ans = Integer.MAX_VALUE;
        int[] memoryArr = new int[n];
        int[] costArr = new int[n];
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        
        int totalCost = 0;
        // 비용과 메모리 초기화 및 총 비용 계산
        for (int i = 0; i < n; i++) {
            memoryArr[i] = Integer.parseInt(st1.nextToken());
            costArr[i] = Integer.parseInt(st2.nextToken());
            totalCost += costArr[i];
        }
        
        int[][] dp = new int[n][totalCost + 1];

        for (int i = 0; i < n; i++) {
            int cost = costArr[i];
            int memory = memoryArr[i];
            
            for (int j = 0; j <= totalCost; j++) {
                // 앱이 하나일 경우 예외처리
                if (i == 0) {
                    if (j >= cost) dp[i][j] = memory;
                } else {
                    if (j >= cost) dp[i][j] = Math.max(dp[i - 1][j - cost] + memory, dp[i - 1][j]);
                    else dp[i][j] = dp[i - 1][j];
                }
                
                // 문제에서 주어진 필요한 메모리보다 확보가능한 메모리가 클 경우 정답으로 저장
                if (dp[i][j] >= m) ans = Math.min(ans, j);
            }
        }
        System.out.println(ans);
    }
}

 

[dp 일차원 배열]

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

public class Main {
    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());

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

        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 totalCost = 0;
        for (int i = 1; i <= N; i++) {
            totalCost += cost[i];
        }

        int[] dp = new int[totalCost + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = totalCost; j >= cost[i]; j--) {
                if (dp[j - cost[i]] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - cost[i]] + memory[i]);
                }
            }
        }

        int result = totalCost;
        for (int i = 0; i <= totalCost; i++) {
            if (dp[i] >= M) {
                result = i;
                break;
            }
        }

        System.out.println(result);
    }
}