[Java] 백준 1943번: 동전 분배

[문제 바로 가기] - 동전 분배

📌 유형 : DP (배낭)

처음엔 금액의 합 절반을 조합으로 풀이하려고 했는데 시간초과가 나서 배낭 문제로 풀이했다.

💡 아이디어

1. 합이 홀수인 경우 똑같이 2로 나눌 수 없기 때문에 0
2. dp 배열을 이용한 배낭 풀이

• dp[금액] = true는 해당 금액을 만들 수 있음
• dp[금액] = false는 해당 금액을 만들 수 없음

dp[k]가 true인 경우는 amount * j인 cost를 더해도 true가 되므로, 이를 반복하면서 만들 수 있는 금액을 찾고 true 해준다.

마지막에 구해야 하는 금액인 dp[mid]가 true라면 1, 아니라면 0을 출력한다.

풀이

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

/**
 * 백준 1943번 동전 분배
 * - 배낭
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		for (int t = 0; t < 3; t++) {
			int N = Integer.parseInt(br.readLine());
			
			int sum = 0;
			
			int[][] coins = new int[N][2];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				int amount = Integer.parseInt(st.nextToken());
				int count = Integer.parseInt(st.nextToken());
				
				coins[i][0] = amount;
				coins[i][1] = count;
				
				sum += amount * count;
			}
			
			if (sum % 2 == 1) {
				System.out.println(0);
				continue;
			}
			
			int mid = sum / 2;
			
			boolean[] dp = new boolean[mid + 1];
			boolean[] tmp = new boolean[mid + 1];
			dp[0] = true;
			
			for (int i = 0; i < N; i++) {
				int amount = coins[i][0];
				int count = coins[i][1];
				
				tmp = dp.clone();
				
				for (int j = 1; j <= count; j++) {
					int cost = amount * j;
					for (int k = 0; k + cost <= mid; k++) {
						if (dp[k]) tmp[k + cost] = true;
					}
				}
				
				dp = tmp;
			}
			
			System.out.println(dp[mid] ? 1 : 0);
		}
	}
}