[JAVA] BOJ 백준 1943 동전 분배

https://www.acmicpc.net/problem/1943

1943번: 동전 분배

문제

윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.

그런데 돈을 받은 윤화와 준희는 좋아하기보다 고민에 빠지고 말았다. 원장선생님께 받은 이 돈을 어떻게 나누어 할지 고민에 빠진 것이다. 두 사람 모두 상대방이 자기보다 1원이라도 더 받는 것은 도저히 인정할 수 없어 한다. 따라서 돈을 똑같이 둘로 나누어 가져야 두 사람이 모두 만족할 수 있게 된다.

하지만 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.

이제 우리가 할 일은 다음과 같다. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.

입력

세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이고, 같은 금액을 가진 동전이 두 번 이상 주어지는 경우는 없다.

출력

첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

💡 개선점
1. sum이 홀수인 경우 정확하게 반으로 나눌 수 없다. 이것을 dp를 갱신한 뒤 체크하게 되면 시간초과가 발생한다.
2. 50000까지만 검사하자! → 어차피 합은 100000을 넘지 않는다. 그렇기 때문에 중간 값은 50000을 넘지 않고 우리는 중간값이 가능한지만 검사하면 된다.
3. 이차원 DP를 사용하지 말고 일차원을 사용하여 뒤에서부터 갱신해준다.
4. int dp말고 boolean을 사용하여 그 가치의 값을 만들수 있는지만 고려한다.

전체 코드

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

public class BOJ_1943 {
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for(int t=0; t<3; t++) {
			boolean[] d = new boolean[50001];
			ArrayDeque<int[]> coins = new ArrayDeque<>();
			d[0] = true;
			int sum = 0;
			int N = Integer.parseInt(bf.readLine());
			for(int u =0; u<N; u++) {
				StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
				int coin = Integer.parseInt(st.nextToken());
				int num = Integer.parseInt(st.nextToken());
				sum += num * coin;
				for(int k = coin; k<=num*coin && k<=50000; k+=coin) {
					d[k] = true;
				}
				coins.offer(new int[] {coin, num, sum});
			}
			if(sum % 2 == 1) sb.append(0).append("\\n");
			else if(d[sum/2]) sb.append(1).append("\\n");
			else {
				while(!coins.isEmpty()) {
					int[] now = coins.poll();
					if(now[2] > 50000) now[2] = 50000;
					for(int i=0; i<now[1]; i++) {
						for(int j=now[2]; j>now[0]; j--) {
							if((j-now[0]) % now[0] == 0 && (j-now[0]) <= now[0]*now[1]) continue;
							d[j] |= d[j-now[0]];
						}
					}
				}
				if(sum % 2 == 0 && d[sum/2]) sb.append(1).append("\\n");
				else sb.append(0).append("\\n");
			}
		}
		System.out.println(sb);
	}
}

한 줄 씩 살펴보자!

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
for(int t=0; t<3; t++) {
	boolean[] d = new boolean[50001];
	ArrayDeque<int[]> coins = new ArrayDeque<>();
	d[0] = true;
	int sum = 0;
	int N = Integer.parseInt(bf.readLine());

세개의 테스트 케이스를 확인해야 하므로 FOR문을 세번 돌린다.

사용할 dp를 선언한다.

ArrayDeque을 이용하여 동전의 가치와 개수, 여태의 합을 넣어준다.

0원은 언제나 가능하기 때문에 true로 바꿔준다.

for(int u =0; u<N; u++) {
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		int coin = Integer.parseInt(st.nextToken());
		int num = Integer.parseInt(st.nextToken());
		sum += num * coin;
		for(int k = coin; k<=num*coin && k<=50000; k+=coin) {
			d[k] = true;
		}
		coins.offer(new int[] {coin, num, sum});
	}

사용할 동전 종류 N개를 입력 받아주고 coins에 넣어준다.

이때 dp를 1차 갱신해주는데 입력받은 동전으로 가능한 가치만! true로 바꾸어준다.

50000까지만 검사하기로 하였기에 제한 조건을 넣는다.(잊으면 ArrayIndexOutOfBounds가 날 것이다.)

if(sum % 2 == 1) sb.append(0).append("\\n");
else if(d[sum/2]) sb.append(1).append("\\n");

sum이 홀 수 인 경우는 불가능한 경우이고 여태의 갱신으로 만들수 있는 가격이면 가능한 경우이면 1을 출력한다.

else {
		while(!coins.isEmpty()) {
			int[] now = coins.poll();
			if(now[2] > 50000) now[2] = 50000;
			for(int i=0; i<now[1]; i++) {
				for(int j=now[2]; j>now[0]; j--) {
					if((j-now[0]) % now[0] == 0 && (j-now[0]) <= now[0]*now[1]) continue;
					d[j] |= d[j-now[0]];
				}
			}
		}
		if(d[sum/2]) sb.append(1).append("\\n");
		else sb.append(0).append("\\n");
	}
}

coins에 넣어있던 동전들을 꺼내서 dp를 갱신한다.

먼저 받아준 sum이 50000이상이면 50000부터만 검사할 수 있게 바꾸어준다. 이때 sum/2으로 바꾸어주어도 된다.

이중 for문을 통해 같은 종류이 동전을 “각각” 살펴 dp를 갱신할 것이다. 이때 1차 dp 갱신과 중복되지 말아야하므로 if문의 조건을 통해 제한을 준다.

d[j-coin]의 값이 true이면 d[j]도 true가 되도록 or를 이용해준다.

sum/2를 살펴 출력을 정해준다.

4가지의 개선을 통해 시간 초과가 나고 에러가 나던 문제를 풀 수 있었다…!