문제 링크

성능 요약

1차 - 메모리: 53500 KB, 시간: 780 ms
2차 - 메모리: 18832 KB, 시간: 140 ms

분류

다이나믹 프로그래밍, 배낭 문제

제출 일자

2025년 1월 17일 13:38:11

문제 설명

우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화 되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직전의 상태를 메인 메모리로부터 읽어 들여 실행 준비를 빠르게 마치기 위해서이다.

하지만 스마트폰의 메모리는 제한적이기 때문에 한번이라도 실행했던 모든 앱을 활성화된 채로 메인 메모리에 남겨두다 보면 메모리 부족 상태가 오기 쉽다. 새로운 앱을 실행시키기 위해 필요한 메모리가 부족해지면 스마트폰의 운영체제는 활성화 되어 있는 앱들 중 몇 개를 선택하여 메모리로부터 삭제하는 수밖에 없다. 이러한 과정을 앱의 ‘비활성화’라고 한다.

메모리 부족 상황에서 활성화 되어 있는 앱들을 무작위로 필요한 메모리만큼 비활성화 하는 것은 좋은 방법이 아니다. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문이다. 여러분은 이러한 앱의 비활성화 문제를 스마트하게 해결하기 위한 프로그램을 작성해야 한다

현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자. 이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.

입력

입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다

단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.

출력

필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다.

풀이

느낀점

• 메모리초과가 걸린적이 별로 없어서 왜 메모리 초과가 나오는지도 스스로 알지 못했다..
• 처음 풀이에서 dp테이블을 2차원 배열 int[][] dp = new int[n][m+1];로 구성했는데 각 정수(int)는 4바이트 이므로 n=100, m=10,000,000일 때 약 3,814.7MB의 메모리가 필요하다는 답변을 받았다. 문제에서 메모리 제한은 128MB이다.
• 따라서 dp테이블을 1차원으로 프로그램의 중복사용을 방지하기 위해 역방향으로 순회하며 갱신했다.
• 그래도 메모리와 시간이 비교적 많이 걸리는 것 같아서, 비용을 기준으로 dp 테이블을 구성했다는 질문게시판에서의 말을 보고 다시 풀어보기로 했다.

1차 설계 : 30분

• Program정보를 배열로 저장하고, memory 기준 오름차순으로 정렬한다.
• dp[0]을 제외한 모든 칸을 INFINITE 값으로 채운다. (최소값으로 갱신해야 하는데, 0메모리를 비우기 위해서는 비용이 0이기 때문)
• 정렬된 프로그램을 순회(i)하며, 0번째 프로그램부터 i번째 프로그램까지 사용할 수 있을때 각 메모리를 비우는데 필요한 최소 재부팅 비용을 갱신한다.
  • 계산하려는 메모리가 i번째 프로그램의 메모리보다 작거나 같은 경우 dp[i]와 i 프로그램의 비용중 작은 값으로 갱신한다.
  • 그렇지 않으면 dp[i-memo] + cost와 dp[i] 값중 더 작은 값으로 갱신한다.
• 이때 dp 테이블 갱신을 역순으로 해야 하는데, 그 이유는 앞에서 해당 순서의 프로그램 비용으로 갱신된 값에 대해 뒤에서 중복으로 사용할 수 있기 때문이다.

코드(Java)

• 1차 구현 시간: 80분
• 메모리: 53500 MB, 시간: 780 ms

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 앱_7579
 * Date: 2025.01.16
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static final int INFINITE = 2_000_000_000;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        Program[] programs = new Program[n];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            programs[i] = new Program(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            programs[i].cost = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(programs);
        int[] dp = new int[m+1];
        Arrays.fill(dp, INFINITE);

        for (int i = 0; i < n; i++) {
            int memo = programs[i].memory;
            int cost = programs[i].cost;
            for (int j = m; j >= 0; j--) {
                if (j <= memo) dp[j] = Math.min(dp[j], cost);
                else dp[j] = Math.min(dp[j-memo] + cost, dp[j]);
            }
        }

        bw.write(String.valueOf(dp[m]));
		bw.flush();
		bw.close();
		br.close();
	}
}

class Program implements Comparable<Program>{
    int memory;
    int cost;

    Program() {}

    Program(int memory) {
        this.memory = memory;
        this.cost = 0;
    }

    @Override
    public int compareTo(Program o) {
        return Integer.compare(this.memory, o.memory);
    }
}

2차 설계 : 20분

• Program정보를 배열로 저장하고, cost 기준 오름차순으로 정렬한다.
• 정렬된 프로그램을 순회(i)하며, 0번째 프로그램부터 i번째 프로그램까지 사용할 수 있을때 특정비용(j)만 사용하여 비울 수 있는 최대 메모리 값을 갱신한다.
  • dp테이블은 [n+1][10001]크기로 설정한다. 이전 상태의 값을 참조하기 때문에 패딩이 필요하며, 하나의 프로그램 비용은 최대 100, 프로그램은 최대 100개이기 때문.
  • 프로그램 순회는 i인덱스, 비용순회는 j로 사용해본다.
  • j가 i프로그램 비용보다 작으면 dp[i][j] = dp[i-1][j]이다.
  • j가 i프로그램 비용보다 크거나 같으면 dp[i][j]는 dp[i - 1][j - i프로그램의 비용] + i프로그램의 메모리 와 dp[i-1][j] 중 더 큰 값으로 한다. (나를 포함하여 가능한 최대 메모리 vs 나를 제외하고 가능한 최대 메모리)
• 이때 dp 테이블 갱신을 역순으로 해야 하는데, 그 이유는 앞에서 해당 순서의 프로그램 비용으로 갱신된 값에 대해 뒤에서 중복으로 사용할 수 있기 때문이다.

코드(Java)

• 2차 구현 시간: 60분
• 메모리: 18832 MB, 시간: 140 ms

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 앱_7579
 * Date: 2025.01.16
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        Program[] programs = new Program[n];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            programs[i] = new Program(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            programs[i].cost = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(programs);
        int[][] dp = new int[n+1][10001];
        int min = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            int memo = programs[i-1].memory;
            int cost = programs[i-1].cost;

            for (int j = 0; j <= 10000; j++) {
                if (j < cost) dp[i][j] = dp[i-1][j];
                else dp[i][j] = Math.max(dp[i-1][j-cost] + memo, dp[i-1][j]);

                if (dp[i][j] >= m) {
                    min = Math.min(min, j);
                    break;
                }
            }
        }

        bw.write(String.valueOf(min));
		bw.flush();
		bw.close();
		br.close();
	}
}

class Program implements Comparable<Program>{
    int memory;
    int cost;

    Program() {}

    Program(int memory) {
        this.memory = memory;
        this.cost = 0;
    }

    @Override
    public int compareTo(Program o) {
        return Integer.compare(this.cost, o.cost);
    }
}