[백준/BOJ] 2629번 : 양팔저울, 2293번 : 동전 1, 7579번 : 앱 (DP, 동적 계획법 중급)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2629번 : '양팔저울', 2293번 : '동전 1', 7579번 : '앱' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 DP, 동적 계획법의 활용에 대한 이해가 필요합니다.

 

 

2629번 : 양팔저울

 

주어진 질량의 추들을 가지고 구슬의 무게를 확인할 수 있는지를 구하는 문제입니다.

점화식을 구해주면 dp로 쉽게 해결이 가능하므로, 관계식을 찾아봅시다.

 

예를 들어 a라는 질량을 i-1개의 추들로 측정이 가능했다고 가정해봅시다.

그러면 새로운 b라는 질량의 i번째 추를 가지고 새롭게 측정 가능한 질량은 b, a+b, |a-b|의 3가지입니다.

 

( i ) b는 말 그대로 구슬의 반대편에 질량 b인 추를 놓고 측정하는 경우를 말합니다.

( ii ) a+b는 i-1개의 추 + i번째 추를 구슬의 반대편에 모두 올려서 측정하는 경우를 말합니다.

( iii ) |a-b|는 a와 b 중 가벼운 것을 구슬 쪽에 올리고, 나머지를 구슬의 반대편에 올려서 측정하는 경우를 말합니다.

 

따라서 위의 3가지를 재귀적으로 계속 배열에 기록해나가며 측정할 수 있는 모든 질량들을 체크해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N, arr[31];
bool dp[31][15001] = {}, check[15001] = {};

void solve(int i, int weight) {
    if(i > N || dp[i][weight]) return;

    dp[i][weight] = true;
    check[weight] = true;

    solve(i+1, weight);
    solve(i+1, weight + arr[i]);
    solve(i+1, abs(weight - arr[i]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    solve(0, 0);

    int Q; cin >> Q;
    while(Q--) {
        int value; cin >> value;
        if(value <= 15000 && check[value]) cout << "Y ";
        else cout << "N ";
    }
}

 

추의 개수는 최대 30개이고, 각 추의 질량은 최대 500g이므로 구슬의 무게인 40,000을 고려해줄 필요 없이 그냥 배열의 최댓값을 15000으로 잡아주면 됩니다.

왜냐하면 어차피 15000보다 큰 질량은 측정이 불가능하기 때문입니다.

 

check[weight]는 weight 크기의 질량을 측정 가능한지의 여부를 저장하는 bool 변수입니다.

dp[i][weight]는 i번째 추까지 사용했을 때 weight의 질량을 측정 가능한지를 저장하는 bool 변수입니다.

 

두 가지를 모두 사용하여 dp를 기록해주어야 수월하게 해결이 가능합니다.

 

 

 

 

2293번 : 동전 1

 

주어진 n가지 가치를 가지는 동전을 조합하여 k원을 만드는 경우의 수를 구하는 문제입니다.

역시 대표적인 DP 문제이며, 점화식을 세우는 것이 핵심입니다.

 

dp[a]를 a원을 만드는 조합의 수라고 정의해봅시다.

i가지 종류의 동전으로 dp[a]를 계산했을 때, i+1번째 종류의 동전으로 dp[a]를 갱신하려면 dp[a - (i번째 동전의 가치)]와 같이 갱신할 수 있습니다.

왜냐하면 a - (i번째 동전의 가치) 원을 만드는 모든 조합에 i+1번째 동전을 추가하여 a원을 만드는 방법을 새로 만들 수 있기 때문입니다.

 

그러면 i+1번째 동전을 2개 치환하는 경우는 어떻게 하냐고 생각하실 수 있습니다.

그러나 이것은 고려하지 않아도 됩니다.

a를 1씩 증가시켜가면서 값을 업데이트하면, dp[(a - (i번째 동전의 가치)) - (i번째 동전의 가치)]에서 갱신된 값을 기반으로 dp[a - (i번째 동전의 가치)] 값이 갱신되기 때문입니다.

 

 

 

위에 제가 정리한 풀이를 읽어보시면 이해하기가 쉬울 것입니다.

예제에서 주어진 1원, 2원, 5원으로 10원을 조합하는 경우의 수를 dp에 기록하면서 풀이한 것입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

    vector<int> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];

    vector<int> dp(K+1); dp[0] = 1;
    for(int i=0; i<N; i++)
        for(int j=arr[i]; j<=K; j++) dp[j] += dp[j - arr[i]];

    cout << dp[K];
}

 

풀이 코드는 위와 같으며, 가장 주의해야할 부분은 j의 범위입니다.

i의 경우에는 동전의 종류에 따라 설정해주면 되고, j는 i번째 동전을 치환할 수 있는 최소 금액인 arr[i]원부터 시작하여, K원까지 돌리면서 모두 갱신해주면 됩니다.

 

 

 

 

7579번 : 앱

 

N개의 앱 중에서 M의 메모리를 확보하기 위해 필요한 최소 비용을 계산하는 문제입니다.

배낭 문제에 해당하는 문제이며, 조건에 따라 주어질 수 있는 메모리의 범위는 아주 크므로 비용을 이용해 dp에 기록할 수 있도록 정의해주어야 합니다.

dp[i][j]를 i번째 앱까지 고려했을 때 j의 비용으로 확보할 수 있는 최대 메모리로 정의하고 dp를 갱신해주면 쉽게 해결 가능합니다.

 

점화식은 배낭 문제와 동일하게 dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + memory[i]로 간단하게 세울 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int dp[101][10001] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    int memory[101], cost[101], sum = 0;
    for(int i=1; i<=N; i++) cin >> memory[i];
    for(int i=1; i<=N; i++) {
        cin >> cost[i];
        sum += cost[i];
    }

    for(int i=1; i<=N; i++)
        for(int j=0; j<=sum; j++) {
            if(cost[i] > j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + memory[i]);
        }

    for(int i=0; i<=sum; i++)
        if(dp[N][i] >= M) {
            cout << i;
            break;
        }
}

 

위의 점화식을 반복문으로 코드를 작성하면 위와 같이 간단하게 구현할 수 있습니다.