BOJ 백준 28082 기계오리 연구
문제 : https://www.acmicpc.net/problem/28082
[ 문제 요약 ]
- 1 ~ K 개 이상의 배터리를 마음대로 사용해 만들 수 있는 전력량의 종류 값을 최대한 많이 구하고,
- 구한 전력량 값의 종류가 몇 개인지, 그리고 그 값이 무엇인지를 출력하는 문제
[ 테스트 케이스 설명 ]
3 2 // 연구실에 있는 배터리 개수 N(1<=500), 장착 가능한 최대 배터리 개수K(1<=min(N,100))
1 100 10// 각 배터리의 전력량(1<=500)
//답
6// N개의 배터리들을 적당히 조합해 장착시 기계 오리가 작동한 전력량의 종류 수 출력
1 10 11 100 101 110// 두번째 줄에 오리가 작동한 전력량들을 공백을 사이에두고 오름차순으로 출력[ 문제 풀이 ]
총 2개의 정답 코드를 제시한다. 처음 코드는 이해하기 쉽게 2차원 dp로 선언한 내용이고, 두 번째 코드는 최적화 한 코드이다.
문제를 간단히 말하면, 배터리 개수 중 1~k를 사용하면서, 만들 수 있는 전력량을 최대한 많이 구하는 것이다.
dp[배터리 종류][나올 수 있는 전력량] = 사용한 배터리 개수(k보다 작으며 최소한으로 배터리를 사용해야 함)
위와 같이 dp를 선언하여 문제를 풀 수 있다. dp[][]에 저장된 값은 사용한 배터리 개수인데, 이때 배터리의 개수가 최소가 되도록 해야 한다.
그 이유는 배터리의 개수를 최소로 해야만 최대한 많은 전력량의 '종류'를 구할 수 있기 때문이다.
예를 들어 배터리 3개의 전력량이 각각 100, 200, 300이라고 하자, 전력량 300을 만드는 방법은
100 + 200과 같이 배터리 2개를 사용하는 방법, 300을 하나만 사용하는 방법으로 2가지이다.
이때 300을 구하기 위해 배터리 개수를 2개를 써버리면, 더 다양한 전력량을 구할 수 없게 된다.(우리는 k 개 이하에서 가장 많은 전력량의 종류 수를 구해야 하므로)
먼저 2차원 배열로 만든 답을 보자
[ 정답 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 연구실에 있는 배터리 개수 N(1<=500)
int K = Integer.parseInt(st.nextToken()); // 장착가능한 최대 배터리 개수K(1<=min(N,100))
int B[] = new int[N + 1];// 배터리 전력량을 담을 배열
int sum = 0;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
sum += B[i] = Integer.parseInt(st.nextToken());
int dp[][] = new int[N + 1][sum + 1];
Arrays.fill(dp[0], 1<<30);
// dp[배터리 종류][나올 수 있는 전력량 최대] = 사용한 배터리 개수(k보다 작아야 함)
dp[0][0] = 0;
for(int i=1; i<=N; i++)
{
for(int j=0; j<=sum; j++)
{
dp[i][j] = dp[i-1][j];// 이전 값 복사
// 과거가 유효한 값인 경우, 과거를 통해 현재를 계산한다. 과거 값(dp[i-1][j-B[i])이 이미 K라면
// 더이상 배터리를 사용할 수 없으므로 if문으로 걸러준다.
if(j>=B[i] && dp[i-1][j-B[i]] < K )
{
dp[i][j] = Math.min(dp[i-1][j-B[i]] + 1, dp[i][j]);
}
}
}
StringBuilder sb = new StringBuilder();
int cnt = 0;
for(int j=1; j<=sum; j++)
{
if(dp[N][j] <= K)
{
++cnt;
sb.append(j).append(' ');
}
}
System.out.println(cnt);
System.out.println(sb);
}
}
현재를 선택하는 게 더 작은지, 선택하지 않는 게 더 작은지를 코드를 통해 구현한다. 아래와 같이 해주면 된다.
dp 점화 식 : dp[i][j] = min(dp[i - 1][j - B[i]] + 1, dp[i][j])
이때 중요한 것은 2차원 배열 중 dp[0] 번째는 큰 값으로 채우고, dp[0][0] 을 0으로 초기화하여 0,0일 때만 유효한 값으로 만들어 주는 게 중요하다.
그리고 2차원 배열이기 때문에 이전 값을 복사 해오는 코드(dp[i][j] = dp[i-1][j])가 반드시 들어가야 한다.
위 와 같이 반복문으로 dp를 N 번째까지 구했다면, N 번째에는 최적화된, 즉 전력량에 따른 필요한 배터리의 개수의 최소가 들어가 있다.
그래서 dp[N] 번째의 전력량을 1부터 sum까지 돌며 K보다 작은 값들을 카운팅 해주고 출력해 주면 정답이다.
위처럼 2차원 dp 배열로 선언하면 코드도 길어지고, 속도가 느린 단점이 있다. 1차원으로 최적화 시킬 수 있다. 또한 배터리 K 개를 사용해 전력량을 만들 때 나올 수 있는 최대 전력량을 딱 알맞게 구해주면 속도를 좀 더 빠르게 할 수 있다.
[ 최적화 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 연구실에 있는 배터리 개수 N(1<=500)
int K = Integer.parseInt(st.nextToken()); // 장착가능한 최대 배터리 개수K(1<=min(N,100))
int B[] = new int[N + 1];// 배터리 전력량을 담을 배열
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
B[i] = Integer.parseInt(st.nextToken());
Arrays.sort(B);
int sum = 0;
for(int i=N-K+1; i<=N; i++)
sum += B[i];
int dp[] = new int[sum + 1];
Arrays.fill(dp, 1<<30);
// [나올 수 있는 전력량 최대] = 사용한 배터리 개수(k보다 작아야 함)
dp[0] = 0;
for(int i=1; i<=N; i++)
{
for(int j=sum; j >= B[i]; j--)
{
// 과거가 유효한 값인 경우, 과거를 통해 현재를 계산한다. 과거 값(dp[j-B[i])이 이미 K라면
// 더이상 배터리를 사용할 수 없으므로 if문으로 걸러준다. 그러나 if문은 없어도 된다.
if(dp[j-B[i]] < K )
{
dp[j] = Math.min(dp[j-B[i]] + 1, dp[j]);
}
}
}
StringBuilder sb = new StringBuilder();
int cnt = 0;
for(int j=1; j<=sum; j++)
{
if(dp[j] <= K)
{
++cnt;
sb.append(j).append(' ');
}
}
System.out.println(cnt);
System.out.println(sb);
}
}
배터리의 전력량을 B 배열에 담고, 정렬해 준 다음, K 개만 더해서 sum을 조금 더 작게 만들어 주어 최적화 시키고,
1차원 dp로 변경하여 이전 값을 복사해올 필요 없이 유효한 값만 빠르게 탐색할 수 있게 하였다.
1차원 dp로 변경 시 주의할 점은, 현재 dp를 갱신함으로써 현재의 결과가 미래의 연산 결과에 영향을 미치지 않아야 한다.
그래서 for 문의 j 값이 초기엔 sum으로 시작하여 점차 감소하는 형태를 띠며 B[i] 값만 큼만 감소하게 하여 문제 조건에 알맞은 연산이 가능하도록 한다.
아래는 차례로 2차원 dp의 실행 시간과 1차원 dp의 실행 시간이다. 약 69% 빨라진다.
