[백준 1943] 동전 분배

배낭문제 응용이다.

 

하지만 처음에 절반인 x를 만들 수 있다면 나머지 동전으로 x를 만들 수 있다는게 보장이 될까? 라는 의문에 사로잡혀

vector로 하나의 절반인 x를 만들때 사용된 동전을 다 저장하고 모든 동전에서 해당 동전들을 빼서 나머지 동전으로 x를 만들 수 있는지 판단하려고 했다.

 

 

2차원 배열로 풀어도 되고 1차원 배열로 풀어도 된다.

이때 1차원 배열로 풀때 무조건 뒤에서부터 갱신해줘야한다.

왜냐하면 앞에서부터 계산해주면 동전의 갯수를 제대로 고려하지 못하기 때문.

 

만약 100이 2개라고 치자.

그리고 만들어야하는 절반은 600이다.

 

이때 1부터 600까지 돌면서 200은 100이 2개이므로 가능하다고 뜰것이다.

그리고 이 이후에는 100의 갯수가 모자라 모두 false여야하는데

300 또는 400 까지 갔을때 200이 true이므로 만들 수 있는 것이라고 판단하게 되는 것이다.

 

따라서 1차원 배열일때는 무조건 뒤에서부터 탐색해야 동전 갯수가 제대로 고려된 답을 얻을 수 있다. 

---

2차원 배열 풀이

#include <iostream>
#include <vector>

#define SIZE 50001
using namespace std;

int N;
int half;

vector<pair<int, int>> v;
bool dp[101][SIZE];

void solve()
{
    // dp 초기화
    for (int i = 0; i <= N; i++)
    {
        for (int k = 0; k <= half; k++)
        {
            dp[i][k] = false;
        }
    }

    for (int i = 0; i <= N; i++)
    {
        dp[i][0] = true;
    }

    int cost, num;
    for (int i = 1; i <= N; i++)
    {
        cost = v[i].first;
        num = v[i].second;

        for (int k = 1; k <= half; k++)
        {
            // 해당 코인을 고려안하고도 만들 수 있으면 true로 바꾸고 스킵
            if (dp[i - 1][k])
            {
                dp[i][k] = dp[i - 1][k];
                continue;
            }

            for (int cnt = 1; cnt <= num; cnt++)
            {
                // 범위 넘어가면 바로 break 더이상 조사할 필요가 없음
                if (k - cost * cnt < 0)
                {
                    break;
                }

                // 만약 직전꺼를 만들 수 있으면 현재꺼도 만들 수 있음
                if (dp[i - 1][k - cost * cnt])
                {
                    dp[i][k] = true;
                }

                if (dp[i][k])
                {
                    break;
                }
            }
        }

        // half 되는 것 찾자마자 종료
        if (dp[i][half])
        {
            cout << "1\n";
            return;
        }
    }

    cout << "0\n";
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int cost, num;
    int total;
    for (int i = 0; i < 3; i++)
    {
        cin >> N;

        // 동전 배열 초기화 및 더미 추가
        v.clear();
        v.push_back(make_pair(0, 0));
        total = 0;

        for (int k = 0; k < N; k++)
        {
            cin >> cost >> num;
            total += cost * num;
            v.push_back(make_pair(cost, num));
        }

        if (total % 2 == 1)
        {
            cout << "0\n";
        }
        else
        {
            half = total / 2;
            solve();
        }
    }
    return 0;
}

 

1차원 배열 풀이

#include <iostream>
#include <vector>

#define SIZE 50001
using namespace std;

int N;
int half;

vector<pair<int, int>> v;
bool dp[SIZE];

void solve()
{
    // dp 초기화
    for (int i = 0; i <= half; i++)
    {
        dp[i] = false;
    }
    dp[0] = true;

    int cost, num;

    // 모든 동전에 대해 고려
    for (int i = 0; i < N; i++)
    {
        cost = v[i].first;
        num = v[i].second;

        // 1차원 배열로 할때는 반드시 뒤에서 앞으로 갱신해야함
        // k를 1부터 half까지 하면 100이 2개인데 앞서 200이 갱신되어 400에서 200이 true니 400을 만들 수 있다고 생각함
        // 즉, num 갯수가 고려되지 않고 무제한으로 가지고 있는 것처럼 처리됨
        for (int k = half; k >= 1; k--)
        {
            // 현재 동전을 사용하지 않고도 만들 수 있는 금액이면 skip
            // 이미 true 라면
            if (dp[k])
            {
                continue;
            }

            for (int cnt = 1; cnt <= num; cnt++)
            {
                // 범위 넘어가면 더 이상 조사할 필요가 없음
                if (k - cost * cnt < 0)
                {
                    break;
                }

                // 전에꺼를 만들 수 있다면 현재꺼 만들 수 있는거임
                if (dp[k - cost * cnt])
                {
                    dp[k] = true;
                    // 더이상 고려 안해도 되니 break
                    break;
                }
            }

            if (dp[half])
            {
                cout << "1\n";
                return;
            }
        }
    }

    cout << "0\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int cost, num;
    int total;
    for (int i = 0; i < 3; i++)
    {
        cin >> N;

        // 동전 배열 초기화
        v.clear();
        total = 0;

        for (int k = 0; k < N; k++)
        {
            cin >> cost >> num;
            total += cost * num;
            v.push_back(make_pair(cost, num));
        }

        if (total % 2 == 1)
        {
            cout << "0\n";
        }
        else
        {
            half = total / 2;
            solve();
        }
    }
    return 0;
}