BOJ 백준 9327 용량 확보
문제 : https://www.acmicpc.net/problem/9327
[ 문제 요약 ]
- 테스트 케이스마다, 목표 용량이 주어지고, 그 용량을 달성하기 위한 초기 디스크들의 용량이 주어진다.
- 특정 디스크를 선택한 경우 그 디스크의 *3만큼 용량이 늘어나는데, 이 때 늘어난 용량이 목표 용량에 도달할 때 선택했던 초기 디스크 용량들의 합을 구하는 문제이다.
[ 테스트 케이스 설명 ]
3 // 테스트 케이스 수(1<=100)
2 500 // 첫줄에는 디스크의 수N(1<=100)와 확보 해야 하는 목표 용량 E(0<=10^9)이 주어짐
500 500 // 각 디스크의 크기 N개가 일렬로 주어짐(1<=2000)
4 2400
400 600 700 1000
2 1000
10 10
// 정답
500
1300
FULL
[ 문제 풀이 ]
총 2개의 정답 코드를 제시한다. 처음 코드는 이해하기 쉽지만 속도가 느리고, 두 번째는 최적화 한 코드이다.
먼저 문제를 단순화 시켜보자. 목표로 하는 용량을 도달할 수 없을 경우는 FULL을 출력한다.
목표로 하는 용량을 달성할 수 없는 경우는 무엇일까?
목표 용량이 1500인데, 주어진 디스크는 2개이고 각각 초기 용량이 100씩이라고 하자, 그럼 둘 다 선택했을 때 얻을 수 있는 용량은 100 * 2 + 100 * 2 = 400이다. (자기 자신의 초기 용량은 문제 조건상 포함시키지 않는다. 그래서 2를 곱함)
위 식을 통해, 초기에 주어진 디스크 용량 값의 2배 한 결과의 합을 통해, 목표로 하는 용량을 만들 수 없을 때 FULL을 출력해야 함을 알 수 있다.
그리고, 추가로 알 수 있는 점은, 주어진 초기 디스크 용량들을 처음부터 2배로 받아 놓고 그 값들을 순차적으로 선택해나가면서 가장 적은 용량들을 선택해나가며 목표 용량을 채워야 함을 알 수 있다.
아래와 같이 dp를 선언하면 간단하게 해결할 수 있다.
dp[디스크 순서][주어진 디스크들의 2배 한 값들의 sum] = 총용량
[ 정답 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());//테스트 메이스 수(1<=100)
while(T-->0)
{
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());// 세트의 수N(1<=100)
int E = Integer.parseInt(st.nextToken());// 추가로 확보 해야하는 목표 용량 E(0<=10^9)이 주어짐
int A[] = new int[N + 1];
int sum = 0;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
sum += A[i] = Integer.parseInt(st.nextToken()) * 2;// 각 세트의 크기 1<=2000
if(sum < E)
{
sb.append("FULL").append('\n');
continue;
}
int dp[][] = new int[N + 1][sum + 1];
for(int i=1; i<=N; i++)
{
for(int j=0; j<=sum; j++)
{
dp[i][j] = dp[i-1][j];
if(j >= A[i])
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-A[i]] + A[i]);
}
}
for(int i=0; i<=sum; i++)
{
if(dp[N][i] >= E)
{
sb.append(i / 2).append('\n');
break;
}
}
}
System.out.print(sb);
}
}
위 코드를 보면, 먼저 초기 디스크 용량들을 입력받을 때 2배 해서 받는다. 그리고 sum에 누적해 주고, sum이 목표 용량 E를 도달할 수 없을 때 FULL을 출력한다.
점화식은, 먼저 자기 이전 선택한 값을 자기에게 복사해 주고, ( dp[i][j] = dp[i-1][j] )
현재 고려 중인 디스크를 선택했을 때와 안 했을 때, 무엇이 더 큰지 max 함수로 최대 값을 갱신해 주면 된다. 현재 디스크를 선택했을 때가 dp[i-1][j-A[i]] + A[i] 이다.
그리고 N 번째가 되면, N번째 행에는 최댓값들이 다 들어가 있을 것이기 때문에 dp[N][0]부터 dp[N][sum]까지 루프를 돌면서 그 안에 목표로 하는 용량 보다 큰 i가 있다면 그것을 답으로 출력해 준다.
그런데 위 정답 코드는 2차원 배열로 해서 느리다, 0/1 배낭 문제는 보통 dp를 1차원으로도 해결할 수 있다.
위에서 자기 이전 선택한 값을 복사해 주는 구간이 있는데 ( dp[i][j] = dp[i-1][j] ), 이게 사실 1차원 배열로 하면 불필요 해진다. 훨씬 속도도 빠르다.
추가로 우리는 입력받을 때부터 2배로 입력받았다. 그러나 사실 입력도 2배를 받을 필요가 없다. 그냥 원래의 값으로 받아놓고, dp에 최댓값만 갱신해 준 다음, 목표 용량(E)과 비교할 때만 결괏값에 2를 곱해줘도 된다.
[ 최적화 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());//테스트 메이스 수(1<=100)
while(T-->0)
{
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());// 세트의 수N(1<=100)
int E = Integer.parseInt(st.nextToken());// 추가로 확보 해야하는 목표 용량 E(0<=10^9)이 주어짐
int A[] = new int[N + 1];
int sum = 0;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
sum += A[i] = Integer.parseInt(st.nextToken());// 각 세트의 크기 1<=2000
if(sum * 2 < E)
{
sb.append("FULL").append('\n');
continue;
}
int dp[] = new int[sum + 1];
for(int i=1; i<=N; i++)
for(int j=sum; j>=A[i]; j--)
dp[j] = Math.max(dp[j],dp[j-A[i]] + A[i]);
for(int i=0; i<=sum; i++)
{
if(dp[i] * 2 >= E)
{
sb.append(i).append('\n');
break;
}
}
}
System.out.print(sb);
}
}
위에서 dp를 연산해 나갈 때 안쪽 for 문을 보면, j는 sum부터 시작하여 A[i]까지 감소한다.
이렇게 하는 이유는, 현재의 계산 결과가 미래에 영향을 미치지 않아야 하기 때문이다.
만약 j 값을 A[i]에서 시작해서 sum까지 증가시키면서 계산한다면, 현재 연산 결과가 미래에 영향을 미치게 된다.
2차원 dp일 경우, 현재 행(dp[i])을 구할 때 항상 이전행(dp[i-1])을 통해 구해왔기 때문에 위와 같은 조건 제한이 필요가 없었지만,
1차원으로 바꿀 경우는 중복 선택을 고려해야 한다.
이건 특정 아이템을 한번 선택할 수 있느냐, 여러 번 선택할 수 있느냐에 따라 달라진다.
지금 문제는 디스크를 한 번만 선택할 수 있었다. 그러나 디스크를 여러 번 선택해도 된다면, 1차원 dp로 구현할 때 sum부터 내려오는 게 아니라 A[i]부터 즉, 작은 숫자부터 sum까지 올라가면서 구해야 될 것이다. (그래야 현재 선택을 여러 번 한 결과까지 고려할 수 있게 되니까)
최적화를 마친 코드와 그렇지 않은 코드의 속도 차이는 아래와 같다.
