[Baekjoon] 1943: 동전 분배

문제

돈이 주어지면 반으로 정확히 나눌 수 있는지 묻는 배낭 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        for (int i = 0; i < 3; i++) {
            System.out.println(distribute() ? 1 : 0);
        }
    }

    private static boolean distribute() throws IOException {
        int[] coins = new int[100001];

        int n = Integer.parseInt(br.readLine());
        int total = 0;
        for (int i = 1; i <= n; i++) {
            String[] input = br.readLine().split(" ");
            int coin = Integer.parseInt(input[0]);
            int count = Integer.parseInt(input[1]);
            for (int j = 0; j <= count; j++) {
                for (int k = total; k >= 0; k--) { // 이전 기록에 영향이 없도록 반대로 탐색
                    if (k + (coin * j) > 100000) { // 합이 100000원이 넘어가면 종료
                        break;
                    }

                    if (coins[k] > 0) { // 동전을 넣은 적이 있으면 현재 가격과 합을 계산하여 기록
                        coins[k + (coin * j)] += 1;
                    }
                }
            }
            for (int j = 0; j <= count; j++) { // 현재 동전 가격 기록
                coins[coin * j] += 1;
            }
            total += coin * count; // 총계 기록
        }

        if (total % 2 != 0) { // 나눠지지 않으면 바로 false 반환
            return false;
        }

        return coins[total / 2] != 0; // 총 값의 반이 기록되어 있는지 여부 반환
    }
}

이 문제는 전형적인 배낭 문제이다. 때문에 현재 동전 값과 이전에 넣었던 동전들과의 합을 계산하여 기록하는 것이 관건이다.

하지만 0부터 순차전으로 반복하게 되면 현재 반복 타임에서 기록된 동전도 확인하게되어 원하지 않는 결과가 나오게 될 수 있다. 따라서 끝에서부터 반대로 탐색하는 것이 좋다.

 

예를 들어, 100원짜리 동전이 2개 들어와 100, 200을 기록할 때

원래대로라면 100원과 200원만 기록되어야 하는데, 전에 기록된 값이 영향을 받아 300에도 기록되는 상황이 생긴다.

위를 고려하며 탐색을 진행하면서 값이 기록된 적이 있다면 그 값에서 현재 동전 값을 더하여 다시 기록해준다.

 

회고

배낭 문제를 풀어봤었지만 기억이 잘 나지 않아 푸는데 오래 걸렸다. 다시 이 유형을 풀어보는 것이 좋을 것 같다.