1943 동전 분배 [JAVA]

문제 풀이

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

 

처음엔 가능한 동전 집합에 다음 동전을 하나씩 더하며 새로운 경우를 추가해가며 전체 금액의 합/2를 만들어 보려 했으나... 메모리 + 시간이 말도안되기에 계속해서 터졌다.

 

갈피를 못잡다 결국 아래 블로그를 보고 이해를 했다

https://blog.naver.com/adamdoha/222086394461

1943번 : 동전 분배

설명이 너무 잘되어 있어 추가 설명은 하지 않겠다..

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int t = 0 ; t<3; t++){
            int n = Integer.parseInt(br.readLine());
            int[][] coinInfo = new int[n][2];

            int total = 0;

            for (int i = 0; i < n; i++) {
                String[] s = br.readLine().split(" ");
                int value = Integer.parseInt(s[0]);
                int count = Integer.parseInt(s[1]);
                coinInfo[i][0] = value;
                coinInfo[i][1] = count;
                total += value*count;
            }

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

            int half = total/2;

            int[] dp = new int[half+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            boolean isMade =false;

            for (int p = 0; p<n; p++) {
                int value = coinInfo[p][0];
                int count = coinInfo[p][1];

                for (int i = 0; i <= half; i++) {
                    if(dp[i] == Integer.MAX_VALUE)
                        continue;

                    if(dp[i] < count){
                        if(i + value == half){
                            isMade=true;
                            break;
                        }else if(i + value < half){
                            dp[i+value] = Math.min(dp[i+value], dp[i]+1);
                        }
                    }
                    dp[i] = 0;
                }
                if(isMade)
                    break;
            }

            if(isMade || dp[half] != Integer.MAX_VALUE){
                System.out.println(1);
            }else{
                System.out.println(0);
            }
        }
    }
}