BOJ_1943_동전 분배

2초니까 DP(Dynamic Programming) 아니겠지? 하고 DFS로 풀었다가 시간 초과 뚜드려 맞고 DP로 푼 문제

1. DP[0] = true
2. 동전의 가치와 개수로 만들 수 있는 금액을 true로 줘서 초기 세팅한다
3. 반복문을 돌면서 true인 곳에(해당 금액을 만들 수 있다는 뜻) 현재 동전(바깥 반복문) * 현재 개수(안쪽 반복문)를 더한 금액을 true로 바꾼다
4. 정확히 절반을 만들었다면 다른 절반도 만들 수 있다는 뜻이 되기 때문에 총액 / 2 를 만들었는지 확인하면 된다

디테일

이전 결과가 다음 결과에 영향을 미치기 때문에 탑다운 방식으로 풀어야 한다. 즉, 큰 금액부터 작은 금액으로 탐색해야 한다
반대로 하게 되면 예를 들어 1원이 1개 있을 때 dp[1원] = true로 주고 2를 만들러 가면 dp[1+1원] = true, dp[2 + 1원] = true ... 이렇게 모든 금액을 1원 1개로 만들 수 있게 되는 기적이 일어난다

금액 탐색 범위는 총액 / 2 - value 이하 0 초과로 했다. 0은 이미 초기 세팅 때 작업해주었고, 총액 / 2 - value 보다 크다면 value 가치의 동전을 1개도 더 더할 수 없기 때문이다

총액이 2로 떨어지지 않으면 둘로 나눌 수 없기 때문에 dp 탐색할 필요 없다
마찬가지로 총액 / 2 가 이미 true라면 dp 탐색하러 갈 필요가 없다

삽질

dp 배열을 50001로 주고 예외처리 안 해서 아웃오브바운드가 떴다 ㅎㅎ 초기 세팅할 때 동전의 배수로 50000을 넘어서까지 만들어질 수도 있기 때문에 50000 넘어가면 마킹 안 하게 했다

package BJO;

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

public class BJO_1943_동전분배 {
    static class Coin {
        int value;
        int count;

        Coin(int value, int count) {
            this.value = value;
            this.count = count;
        }
    }

    static int answer = 0;
    static int money = 0;
    static Coin[] coins;
    static boolean[] dp;

    /*
    dp 배낭 문제
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        for (int t = 0; t < 3; t++) {
            int N = Integer.parseInt(br.readLine());
            answer = 0;
            money = 0;
            coins = new Coin[N];
            dp = new boolean[50001]; // 최대 금액이 10만이다 절반만 보면 된다
            dp[0] = true;

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int value = Integer.parseInt(st.nextToken());
                int count = Integer.parseInt(st.nextToken());

                // 총합을 구한다
                money += value * count;
                Coin coin = new Coin(value, count);
                coins[i] = coin;

                // 동전 가치의 개수 배수를 다 true로 준다
                for (int j = 1; j <= count; j++) {
                    if (value * j > 50000) {
                        break;
                    }
                    dp[value * j] = true;
                }
            }

            if (money % 2 == 0) { // 최종 금액이 2의 배수가 아니면 반으로 나눌 수 없음
                if (dp[money / 2]) {
                    answer = 1;
                } else {
                    dp(N, money);
                }
            }

            sb.append(answer).append('\n');
        }
        System.out.println(sb);
    }

    static void dp(int n, int money) {
        for (int i = 0; i < n; i++) {
            int value = coins[i].value;
            int count = coins[i].count;

            for (int j = money / 2 - value; j > 0; j--) {
                if (dp[j]) {
                    for (int k = 1; k <= count && j + value * k <= money / 2; k++) {
                        dp[j + value * k] = true;

                        if (j + value * k == money / 2) {
                            answer = 1;
                        }
                    }
                }
            }
        }
    }
}