WonYong-Jang
commented
5 years ago 관련 문제
동전 0 - https://www.acmicpc.net/problem/11047
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.- 아래의 조건이 있기에 그리디 알고리즘 사용 가능 ( 배수이기 때문에 큰 동전부터 처리 가능!)
- 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
- 예외 1398 백준 / 동전이 1, 10, 25 ,100 ... 이기 때문에 불가능!
- 그리디 알고리즘
-
dp 로는 해결 불가
public class baek11047 { static int N, K, result; static int[] coin = new int[11]; public static void main(String[] args) throws IOException { N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); for(int i=1; i<= N; i++) { st = new StringTokenizer(br.readLine()); coin[i] = Integer.parseInt(st.nextToken()); } result = 0; // 최소 갯수 // 큰 동전부터 먼저 계산 for(int i=N; i>=1; i--) // 그리디 알고리즘 { if(K < coin[i]) continue; if(K == 0) break; result += K/coin[i]; K %= coin[i]; } System.out.println(result); } }
동전 1 - https://www.acmicpc.net/problem/2293
public class baek2293 {
static int N, K;
static int[] coin = new int[101]; // 보유한 동전 종류
static int[][] dp = new int[101][10001];
// N(n, k) : 거스름돈 K 원을 n개의 동전으로 만들수 있는 조합의 수
public static void main(String[] args) throws IOException {
for(int i=1; i<= N; i++)
{
st = new StringTokenizer(br.readLine());
coin[i] = Integer.parseInt(st.nextToken());
dp[i][0] = 1;
// 거스름돈 k를 k-coin[i] 했을때 0이 나온 경우는 딱 맞게 거슬러줄수 있는 경우의 수
}
int num = 0;
// 가진 동전들의 조합의 수
//ex) 1을 만들수 있는 가짓수를 구해놓고 2를 만들수 있는 수 구할때 1을 만든 가짓수를 더해가면서 구함
for(int i=1; i<= N; i++)
{
for(int j=1; j<= K; j++) // 구할 거스름돈 가격
{
if(j - coin[i] < 0) num = 0; // base case
else num = dp[i][j-coin[i]]; // 동전 coin[i] 으로 만들수 있는 경우
dp[i][j] = dp[i-1][j] + num; // 이전에 만들어 놓은 갯수와 축적
}
}
System.out.println(dp[N][K]);
}
}
메모리 절약 방법 !
dp[0] = 1;
int num = 0;
// 가진 동전들의 조합의 수
//ex) 1을 만들수 있는 가짓수를 구해놓고 2를 만들수 있는 수 구할때 1을 만든 가짓수를 더해가면서 구함
for(int i=1; i<= N; i++)
{
for(int j=1; j<= K; j++) // 구할 거스름돈 가격
{
if(j - coin[i] < 0) num = 0; // base case
else num = dp[j-coin[i]]; // 동전 coin[i] 으로 만들수 있는 경우
dp[j] += num; // 이전에 만들어 놓은 갯수와 축적
}
}동전 2 - https://www.acmicpc.net/problem/2294
public class Main {
static final int INF = 987654321;
static int N, K;
static int[] coin = new int[105];
static int[] coinCnt = new int[10005]; // 최소 동전 갯수 저장 배열
static int[] lastCoin = new int[10005]; // 마지막 사용 동전 기록 ( 어느 동전 썻는지 확인 가능 )
public static void main(String[] args) throws IOException {
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
for(int i=1; i<= N; i++)
{
st = new StringTokenizer(br.readLine());
coin[i] = Integer.parseInt(st.nextToken());
}
for(int i=1; i<= K; i++)
{
coinCnt[i] = INF;
for(int j=1; j<= N; j++)
{
if(i - coin[j] >= 0)
{
if(coinCnt[i] > coinCnt[i-coin[j]] + 1)
{
coinCnt[i] = coinCnt[i-coin[j]] + 1;
lastCoin[i] = coin[j];
}
}
}
}
if(coinCnt[K] == INF) System.out.println(-1);
else System.out.println(coinCnt[K]);
}
public static int min(int a, int b) { return a > b ? b : a; }
}
관련 문제
백준 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