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 + 10001, 987654321);
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 |
댓글 없음:
댓글 쓰기