문제 링크
문제
티어: 골드 2
알고리즘: dp, 배낭
윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.
그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.
하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.
이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.
입력
세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이고, 같은 금액을 가진 동전이 두 번 이상 주어지는 경우는 없다.
출력
첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.
풀이
각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력해야 한다.
일단, 받은 총 금액을 계산한다. 반으로 나눴을 때 딱 떨어지지 않는다면, 그 경우는 0이다.
반으로 나눠진다면, 그 반이 target 금액이 된다.
A, B, C, D 종류가 있다고 해보자,
A ~ C까지
만들 수 있는 금액이 여러 가지 있을 것이다.
그리고 이번에 D 동전을 사용한다고 했을 때
만들지 못한 금액을 D 동전으로 가능한지 시도해 볼 수 있다.
그래서 만들지 못한 금액을 하나씩 탐색하면서, D동전을 1개부터 ~ 최대개수까지 사용했을 때 만들 수 있다면 true로 체크해 주면 된다.
예를 들어 A ~ C까지 동전을 사용했는데, 1000을 만들지 못했다면
이번 D라는 동전에서 1000을 만들 수 있는지 보는 것이다.
D가 100원에 30개가 있고, 만약 3개를 사용해 본다면
dp[1000 - 100 x 3]가 true인지 보면 된다.
이때 dp는 1차원 boolean 배열이기 때문에 현재 동전 개수의 영향을 받지 않으려면 for문을 target ~ 1순으로 돌려야 한다.
왜냐하면 1 ~ target으로 돌렸을 때 현재 동전 3개를 사용해서 dp[300]을 true로 하고,
dp[600]일 때도 동전 3개를 사용해서 dp[300]을 체크한다면, 결과적으로 현재 동전을 6개 사용하게 된다.
그래서 target ~ 1 순으로 돌려야 간섭이 없기 때문에 의도한대로 동전의 개수를 사용할 수 있다.
다음은 더 효율적인 방법의 풀이다.
이번에 dp는 boolean이 아닌 2차원 배열이다.
dp[N][target]이고, 예를 들어 dp[3][300]이라면, 1 ~ 3번째 동전까지 사용했을 때 300을 만드는데 사용된 3 번째 동전의 개수가 된다.
이런 식으로 dp를 체크해 주면, 1부터 동전의 개수만큼 for문을 돌리지 않아도 된다.
예를 들어 target이 50000이고, 현재 동전의 종류가 3 번째라고 해보자, (3 번째 동전은 100 30)
1부터 50000까지 for문을 돌리는데,
dp[3 - 1][300]이 존재한다면, 값을 0을 넣어준다. 3 번째 동전을 0개 사용했다는 의미다.
만약 존재하지 않는다면,
이번엔 3 번째 동전을 사용해 보는 것이다.
이때 dp[3][200]의 값이 0보다 크거나 같은지 딱 한 번만 체크해 보면 된다.
왜냐하면 dp[3][200]이 0이라면, 3 번째 동전이 0개 사용된 것이고, 동전 하나를 사용하면 dp[3][300]을 만들 수 있기 때문이다.
그런데 0보다 크다면 3 번째 동전이 여러 개 사용되었다는 의미고, 그 동전 하나를 추가했을 때 최대 개수를 넘지 않는지만 체크하면 된다.
만약 초깃값인 -1이라면 3 번째 동전을 사용하더라도 dp[3][200]을 만들 수 없다는 의미고, 이때 동전의 개수를 여러 개 사용한다고 해도, 이미 dp[3][200]을 구할 때 체크를 했기 때문에 dp[3][300]도 -1이 되는 것이다.
그래서 동전 하나만 사용해서 가능한지를 체크해 줄 수 있는 것이다. (전에 상태에서 이미 동전을 여러 개 사용했을 수 있기 때문에 정확히 한 개는 아니지만, 반복 횟수 1번으로 가능하다는 의미다.)
이 방식은 2중 for문으로 문제를 풀 수 있다.
소스 코드
import java.io.*;
import java.util.*;
class Coin {
int cnt, v;
Coin(int v, int cnt) {
this.v = v;
this.cnt = cnt;
}
}
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
for(int t=1; t<=3; t++) {
int N = Integer.parseInt(br.readLine());
Coin[] coins = new Coin[N + 1];
int sum = 0; //총 합.
for(int i=1; i<=N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int v = Integer.parseInt(st.nextToken());
int cnt = Integer.parseInt(st.nextToken());
sum += (v * cnt);
coins[i] = new Coin(v, cnt);
}
if(sum % 2 != 0) {
//정확히 반으로 나누어지지 않는다면 불가능.
sb.append(0).append("\n");
continue;
}
//나누어진다면
int target = sum / 2;
int[][] dp = new int[N + 1][target + 1]; //각 종류의 사용된 개수를 저장할 것임.
//-1로 초기화
for(int i=0; i<=N; i++) {
for(int j=1; j<=target; j++) {
dp[i][j] = -1;
}
}
for(int i=1; i<=N; i++) {
for(int j=1; j<=target; j++) {
if(dp[i - 1][j] != -1) {
//-1이 아니라면 0개로 가능.
dp[i][j] = 0;
} else {
//불가능하다면, 현재 동전으로 채울 수 있는지 확인.
if(j - coins[i].v >= 0) {
int useCnt = dp[i][j - coins[i].v]; //사용된 코인의 개수.
if(useCnt != -1) {
//존재한다면 가능성이 있음. -1이라면 불가능함.
if(useCnt + 1 <= coins[i].cnt) {
//하나를 추가적으로 더 사용했을 때 가능하다면.
dp[i][j] = useCnt + 1;
}
}
}
}
}
}
if(dp[N][target] != -1) {
sb.append(1).append("\n");
} else {
sb.append(0).append("\n");
}
}
System.out.println(sb.toString().trim());
}
}