백준 - 동전 분배 (1943) : JAVA

문제 유형
dp

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 윤화와 준희는 솔선수범하여 쓰레기를 줍는 착한 일을 하였다. 원장선생님께서는 윤화와 준희를 칭찬하시고 과자나 사 먹으라고 하시며 동전 몇 개를 윤화와 준희에게 건네 주었다.
2. 두 사람에게 돈을 똑같이 나누는 것이 불가능한 경우도 있다. 예를 들어 500원짜리 1개와 50원짜리 1개를 받았다면, 이 돈을 두 사람이 똑같이 나누어 가질 수는 없다. 물론 동전을 반으로 잘라서 나누어 가질 수도 있겠지만 그러면 돈으로서의 가치를 잃기 때문에 그렇게 할 수는 없다.
3. 원장 선생님께서 N가지 종류의 동전을 각각 몇 개씩 주셨을 때, 그 돈을 반으로 나눌 수 있는지 없는지 판단하는 것이다.
4. 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류  N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선생님께서 주신 금액의 총 합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이고, 같은 금액을 가진 동전이 두 번 이상 주어지는 경우는 없다.
5. 첫째 줄부터 세 줄에 걸쳐, 각 입력에 대하여 반으로 나누는 것이 가능하면 1, 불가능하면 0을 출력한다.

이 문제는 냅색으로 풀 수 있습니다. 사용개수가 제한되기 때문에 역방향으로 탐색해서 구현하도록 했습니다.

int total = 0;

for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());

    int value = Integer.parseInt(st.nextToken());
    int cnt = Integer.parseInt(st.nextToken());

    total += value * cnt;

    list.add(new Money(value, cnt));
}

if (total % 2 != 0) {
    System.out.println(0);
    continue;
}

int[] dp = new int[total / 2 + 1];

dp[0] = 1;

for (Money cur: list) {
    for (int i = total / 2; i >= 0; i--) {
        if (dp[i] == 0) continue;
        for (int j = 1; j <= cur.cnt; j++) {
            int idx = i + j * cur.value;
            if (idx <= total / 2) dp[idx] += dp[i];
        }
    }
}

핵심 코드는 위와 같습니다.

하나 고민이 되었던 것은 이론적인 시간복잡도가 O(N * 50,000 * 100,000)라는 것입니다.
결론적으로 시간초과는 나지 않았는데, 사실상 시간초과가 나는 것이 불가능하기 때문입니다.

일단 동전 개수의 최대는 100,000인데 이는 동전 1만 사용할때만 가능합니다. -> 이때 시간 복잡도는 O(50,000 + 100,000)입니다.

시간 복잡도
O(N * 50,000 * 100,000)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;



class Money {
	int value;
	int cnt;
	
	Money(int value, int cnt) {
		this.value = value;
		this.cnt = cnt;
	}
}
public class Main {
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        for (int t=0; t<3; t++) {
        	
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	
        	int n = Integer.parseInt(st.nextToken());
        	
        	List<Money> list = new ArrayList<>();
        	
        	int total = 0;
        	
        	for (int i=0; i<n; i++) {
        		st = new StringTokenizer(br.readLine());
        		
        		int value = Integer.parseInt(st.nextToken());
        		int cnt = Integer.parseInt(st.nextToken());
        		
        		total += value * cnt;
        		
        		list.add(new Money(value, cnt));
        	}
        	
        	if (total % 2 != 0) {
        		System.out.println(0);
        		continue;
        	}
        	
        	int[] dp = new int[total / 2 + 1];
        	
        	dp[0] = 1;
        	
        	for (Money cur : list) {
        		for (int i=total/2; i>=0; i--) {
        			if (dp[i] == 0) continue;
        			for (int j=1; j<=cur.cnt; j++) {
        				int idx = i + j * cur.value;
        				if (idx <= total / 2) dp[idx] += dp[i];
        			}
        		}
        	}
        	
        	if (dp[total/2] != 0) {
        		System.out.println(1);
        	}
        	else System.out.println(0);
        	
        	
        }
        
    }
    

}