[백준] 동전 분배 1943번 (java) dp

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

 

풀이 방법

 

이 문제는 냅색 문제 유형에 속한다. 주어진 동전의 종류와 각 동전의 개수를 사용해 두 사람이 같은 금액을 만들 수 있는지 확인해야 한다. 이를 해결하기 위해 DP(동적 계획법)을 사용한다.

 

1. 총금액 확인

• 먼저 주어진 모든 동전의 금액을 계산하여 총합 sum을 구한다.

• 만약 총금액이 홀수라면 두 사람이 같은 금액을 가질 수 없으므로, 바로 0을 출력한다. 이는 두 사람이 나눠가질 금액이 정확히 sum / 2가 되어야 하기 때문이다.

한 사람이 sum/2 금액을 만들 수 있으면 나머지 사람은 남은 돈을 다 가져가면 sum/2가 되므로 자연스럽게 문제가 해결된다. 그러므로 sum/2를 구하는 경우만 생각하면 된다.

 

2. DP 배열 설정

•dp [i][j]를 다음과 같이 정의한다:

• i번째 동전까지 사용하여 금액 j를 만들 수 있는지 여부를 나타낸다.

• 값은 1(True) 또는 0(False)으로 저장된다.

• 이를 통해 동전 조합으로 특정 금액을 만들 수 있는지 확인할 수 있다.

3. DFS와 DP의 결합

• 동전 정보를 바탕으로 DFS를 수행해 가능한 금액 조합을 탐색한다.

• 이미 계산된 결과를 저장한 dp 배열을 활용해 중복 계산을 방지하고 효율성을 높인다.

4. 결과 계산

• DFS 탐색 결과, 금액 sum / 2를 만들 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력한다.

 

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


public class P_1943 {
    static int n, sum;
    static int[][] dp = new int[101][100001]; // i번째 포함 이후 사용해서 j 돈을 만들 수 있는가 트루 false
    static ArrayList<ArrayList<Integer>> coin;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void input() throws IOException{
        for (int i = 0;i < 101;i++) {
            Arrays.fill(dp[i], -1);
        }
        coin = new ArrayList<>();
        sum = 0;
        n = Integer.parseInt(br.readLine());
        int a, b;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            sum += (a * b);
            ArrayList<Integer> list = new ArrayList<>();
            list.add(a);
            list.add(b);
            coin.add(list);
        }
    }
    public static int dfs(int idx, int money) {
        if (money < 0) return 0;
        if (money == 0) return 1;
        if (idx >= coin.size()) return 0;
        if (dp[idx][money] != -1) return dp[idx][money];
        int ret = 0;

        for (int i = 0;i <= coin.get(idx).get(1);i++) {
            ret = Math.max(ret, dfs(idx+1, money-coin.get(idx).get(0) * i));
        }
        dp[idx][money] = ret;
        return ret;
    }
    public static void main(String[] args) throws IOException{
        for (int i = 0;i < 3;i++) {
            input();
            if (sum % 2 == 1) {
                System.out.println(0);
            }
            else {

                System.out.println(dfs(0, sum/2));
            }
        }
    }
}

 

개선할 점

다음엔 coin을 클래스로 받아보자