쌉쌀한 무화과의 개발로그

[문제]

우리는 스마트폰을 사용하면서 여러 가지 앱(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 바이트를 확보하기 위한 앱 비활성화의 최소의 비용을 계산하여 한 줄에 출력해야 한다. 

[예제]

>문제 이해

어우 문제가 뭐가 이렇게 긴지...ㅎㅎ

배열의 사이즈 N과 필요한 메모리의 양 M이 먼저 주어집니다.

그리고 두번째 줄에 memory[N]과 세번째 줄에 cost[N]이 차례로 주어집니다.

이제 최소 비용으로(cost) M이상의 메모리를 만드는 방법을 찾아야 합니다.

이 때 cost를 출력하면 되는 문제

>문제 풀이

 1차원 배열 dp[]를 선언하는데, []괄호 안에는 비용이 들어갑니다.

입력 조건에 따라 10000이 최대이긴 하지만, 저는 sum을 구해서 dp= new int[sum]으로 선언했습니다.

예제로 dp가 어떻게 되는지 알아보겠습니다.

cost의 합(sum)= 15 -> dp[15]

	//dp
	dp= new int[sum+1];
	for(int i=0; i<N; i++) {
		for(int j=sum; j>=cost[i]; j--) {
			dp[j]=Math.max(dp[j], dp[j-cost[i]]+memory[i]);
		}
	}

dp[j]는 j만큼의 비용을 가지고 있었을 때, 가질 수 있는 메모리의 최대값을 담은 배열값입니다.

점화식: dp[j]=Math.max(dp[j], dp[j-cost[i]]+memory[i]);

다음은 for문의 반복에 따라 dp[]값의 변화입니다.

*두번째 for문에서 sum~cost[i]로 j-- 반복을 하는 이유는,

j-cost[i]<j로 dp[j]값에 dp[j-cost[i]]가 영향을 미치기 때문에 뒤의 값부터 갱신을 시작해야합니다.

이렇게 dp배열을 전부 채우고 나면,

dp[i]>=M가 되는 i를 찾아 출력해주면 됩니다.

>전체 코드

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

public class Main {
	
	public static void main(String [] args) throws IOException {
		int N, M, sum=0;
		int memory[], cost[], dp[];
		
		//입력받기
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		N= Integer.parseInt(st.nextToken());
		M= Integer.parseInt(st.nextToken());
		memory= new int[N];
		cost= new int[N];
		
		st= new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			memory[i]= Integer.parseInt(st.nextToken());
		}
		
		st= new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			cost[i]= Integer.parseInt(st.nextToken());
			sum+=cost[i];
		}
		
		//dp
		dp= new int[sum+1];
		for(int i=0; i<N; i++) {
			for(int j=sum; j>=cost[i]; j--) {
				dp[j]=Math.max(dp[j], dp[j-cost[i]]+memory[i]);
			}
		}
		
		//출력
		for(int i=0; i<=sum; i++) {
			if(dp[i]>=M) {
				System.out.println(i);
				break;
			}
		}
		br.close();
	}
}

www.acmicpc.net/problem/7579

[문제]

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

[입력]

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

[출력]

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

[예제]

>문제 풀이

간단히 문제를 요약하자면, N개의 추가 주어지고, M개의 질문들이 주어진다.

boolean dp 배열에 N개의 추를 조합하여 만들 수 있는 값들은 dp[값]=true로 설정해준다.

질문에 따라 dp배열 값이 true면 Y를, false이면 N을 출력해주면 된다.

dp의 메모이제이션과 dfs를 모두 써서 풀었다. (for문으로만 풀 수도 있지만, 나는 dfs를 썼다.)

bottom-up으로 arr[i] 값을 더했을 때, 더하지 않았을 때, 빼주었을 때를 각각 재귀로 돌렸다.

(무슨 말인지는 코드를 보면 더 이해하기 쉬울 것이다.)

	public static void find_dp(int idx, int weight) {
		if(dp[idx][weight]) return;
		dp[idx][weight]=true;
		if(idx==N) return;
		
		find_dp(idx+1, weight+arr[idx+1]);
		find_dp(idx+1, weight);
		find_dp(idx+1, Math.abs(weight-arr[idx+1]));
	}

이 부분이 이 문제를 풀기위한 핵심 아이디어? 코드 부분이다.

*이 문제를 풀 때 주의할 점이 몇가지 있는데,

• 추의 개수 30개, 추 1개의 최대무게는 500g >>즉, 15000이 만들 수 있는 무게의 최대값이다.
  그러나, 질문할 수 있는 무게값의 최대는 40000이다.
  질문을 받고 dp[질문한 무게]값이 true인지 아닌지 확인할 때 ArrayIndexOutOfBoundsException이 발생할 수 있다.
• 또한 문제의 입력을 받는데 Scanner를 사용, 출력할 때 System.out.print()를 사용하게 되면 시간초과가 발생한다.나는 입력에서는 BufferedReader와 StringTokenizer 그리고 출력에서는 StringBuilder를 사용했다.

>전체 코드

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

public class Main {
	static int N, M, question, max=15000, arr[];
	static boolean dp[][];
	
	public static void main(String [] args) throws IOException {
		
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		N= Integer.parseInt(br.readLine());
		arr= new int[N+1];
		dp= new boolean[31][max+1];
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			arr[i]= Integer.parseInt(st.nextToken());
		}
		
		find_dp(0,0);
		
		StringBuilder sb= new StringBuilder();
		M= Integer.parseInt(br.readLine());
		st= new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			question= Integer.parseInt(st.nextToken());
			if(question>15000)  sb.append("N ");
			else sb.append(dp[N][question]?"Y ":"N ");
		}
		System.out.println(sb);
		br.close();
	}
	
	public static void find_dp(int idx, int weight) {
		if(dp[idx][weight]) return;
		dp[idx][weight]=true;
		if(idx==N) return;
		
		find_dp(idx+1, weight+arr[idx+1]);
		find_dp(idx+1, weight);
		find_dp(idx+1, Math.abs(weight-arr[idx+1]));
	}
}

문제출처: https://www.acmicpc.net/problem/2629