2017년 3월 16일 목요일

(DP - 동전 문제) 11047 동전0

백준 11047 동전0 https://www.acmicpc.net/problem/11047
         2293 동전1 https://www.acmicpc.net/problem/2293
         2294 동전2 https://www.acmicpc.net/problem/2294
         7579 앱 https://www.acmicpc.net/problem/7579
         1660 캡틴 이다솜 https://www.acmicpc.net/problem/1660
         4781 사탕 가게 https://www.acmicpc.net/problem/4781
         9084 동전 https://www.acmicpc.net/problem/9084
         2624 동전 바꿔주기 https://www.acmicpc.net/problem/2624
         2629 양팔저울 https://www.acmicpc.net/problem/2629
         1398 동전 문제 https://www.acmicpc.net/problem/1398

나는 DP쪽에서도 동전분배하기, 수열 문제에서 많이 취약하다. 많은 노력을 해야겠다.

1. 동전 0

사실상 이문제는 DP문제는 아니다. 실생활에서도 슈퍼마켓을 갔을 때 이러한 문제를 경험할 수 있다. 문제의 조건이 간단하기 때문에 쉽게 풀 수 있다.
$K$원을 만드는 최소 동전 개수를 구하는 문제인데 동전의 가치 ${A}_{i}$가 ${A}_{i-1}$의 배수이기 때문이다.

즉 탐욕알고리즘을 사용해서 가장 큰 동전부터 만드려는 $K$원을 채워 나가면 되겠다.


2. 동전 1

$n$가지 동전으로 $K$원을 만드는 경우를 찾는 문제이다. 동전은 무한대로 사용할 수 있다.
$K$원을 만드는 경우를 DP[K]라고 했을 때 2중 for문을 돌리면서 $K$원까지 만들 수 있는 경우를 채워넣으면 된다.

DP[K] += DP[K-coin[n]]

#include <cstdio>
#include <algorithm>
using namespace std;
int arr[10001],dp[10001];
int main(){
    int N, K;
    scanf("%d%d"&N, &K);
    for (int n = 1; n <= N; n++)
        scanf("%d"&arr[n]);
    sort(arr, arr + N);
    dp[0= 1;
    for (int n = 1; n <= N; n++)
        for (int m = arr[n]; m <= K; m++)
            dp[m] += dp[m - arr[n]];
    printf("%d\n", dp[K]);
    return 0;
}

cs


3. 동전 2

이번에는 $K$원을 만드는 동전의 최소개수를 찾는 문제이다. 동전0과 동전1을 합친문제라고 보면 되겠다.
난 바보같이 DP값을 저장한 후에 저장된 DP값중에서 다시 연산하여 DP값에 다시 저장시켜 2중 for문을 2번이나 사용하는 불필요한 코딩을 했다...

#include <cstdio>
#include <algorithm>
using namespace std;
int arr[10001],dp[10001];
int main(){
    int N, K;
    scanf("%d%d"&N, &K);
    for (int n = 1; n <= N; n++)
        scanf("%d"&arr[n]);
    sort(arr, arr + N);
    for (int n = 1; n <= N; n++){
        for (int m = arr[n]; m <= K; m+=arr[n]){
            if (dp[m] > 0)
                dp[m] = (dp[m] < dp[m - arr[n]] + 1) ? dp[m] : dp[m - arr[n]] + 1;
            else
                dp[m] = dp[m - arr[n]] + 1;
        }
    }
    for (int n = 1; n <= K; n++){
        for (int m = 1; n + m <= K; m++){
            if (dp[n] != 0 && dp[m] != 0){
                if (dp[n + m] > 0)
                    dp[n + m] = (dp[n + m] < dp[n] + dp[m]) ? (dp[n + m]) : (dp[n] + dp[m]);
                else
                    dp[n + m] = dp[n] + dp[m];
            }
        }
    }
    if (dp[K])
        printf("%d\n", dp[K]);
    else
        printf("-1\n");
    return 0;
}



cs
그럴 필요 없이 처음에 DP값을 infinite로 채워넣으면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int arr[10001],dp[10001];
int main(){
    int N, K;
    scanf("%d%d"&N, &K);
    for (int n = 1; n <= N; n++)
        scanf("%d"&arr[n]);
    sort(arr, arr + N);
    fill(dp, dp + 10001987654321);
    for (int n = 1; n <= N; n++){
        dp[arr[n]] = 1;
        for (int m = arr[n] + 1; m <= K; m++)
            dp[m] = min(dp[m], dp[m - arr[n]] + 1);
    }
    if (dp[K])
        printf("%d\n", dp[K]);
    else
        printf("-1\n");
    return 0;
}
cs

4. 앱
앱을 지우는데 드는 비용과 지워지는 메모리 양이 주어진다.
M 이상의 메모리를 지우는데 최소의 비용을 구하는 문제이다.
우리가 지워야 하는 M의 범위가 상당히 크기때문에 다른 관점으로 풀어야 한다.
비용과 앱의 개수가 작기때문에 비용에 따른 메모리를 최대화 하게끔 만들면 된다.
#include <cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
int N, M;
int mem[101], cost[101];
int dp[10101];
int main(){
    int cost_sum = 0;
    scanf("%d%d"&N, &M);
    for (int n = 1; n <= N; n++)
        scanf("%d"&mem[n]);
    for (int n = 1; n <= N; n++)
        scanf("%d"&cost[n]), cost_sum += cost[n];
    for (int n = 1; n <= N; n++){
        for (int c = cost_sum; c >= cost[n]; c--){
            dp[c] = max(dp[c], dp[c - cost[n]] + mem[n]);
        }
    }
    int ans;
    for (int c = 0; c <= cost_sum; c++){
        if (dp[c] >= M){
            ans = c;
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}
cs

댓글 없음:

댓글 쓰기