Easy is Perfect

[백준] 2294번 C/C++ 풀이 _ 동전 2

  • melonicedlatte
  • Aug 11, 2018


출처 : https://www.acmicpc.net/problem/2294 

동전 2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB194715244365026.442%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)

입력

첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 1 

3 15
1
5
12

예제 출력 1 

3

출처

알고리즘 분류

풀이 

dp 를 사용하여 bottom_up 방식으로 해결했다.
dp 벡터와 coin 벡터를 각각 K+1, N+1 크기별로 선언한다. 
dp 는 INF 로 모두 초기화하고, coin 은 0으로 초기화한다.

dp[a] 는 '구하고자 하는 가격이 a 일 때, 필요한 동전의 최소개수'로 정의한다.

먼저 동전을 전부 입력 받은 다음에 해당 동전이 가진 값이 K를 초과하면 버린다 (이 걸 안해서 한 번 런타임 에러가 뜸)
아닌 경우에는 dp의 해당 인덱스를 1로 해준다.(동전 1개로도 가능하다는 뜻)

그 다음 for문을 통해서 k의 인덱스가 1일때부터 모든 동전의 값을 확인하면서 다음 dp 의 인덱스인 next_dp_idx를 갱신한다. 

값이 a고 현재의 동전의 값이 b 라면 dp.at(a + b) 의 값을 확인 한다. 
dp.at(a+b) 는 a+b원일 때, 필요한 동전의 최소 개수이다. 

dp.at(a) + 1 이 현재 a 가격에서 b원 짜리 동전을 사용했을 때, 들어가는 동전의 개수이다. 
이 때, dp.at(a+b) 와 비교하여 더 적을 때 갱신해준다. 

시간 복잡도는 O(N*K) 정도가 나온다. 

더욱 자세한 풀이는 소스코드로 보면 이해할 수 있다. 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
 
int main(){
    // init
    int N, K;
    scanf("%d %d", &N , &K);
    vector< int > coin_vec(N+1, 0);
    vector< int > dp(K+1, INF);
 
    // coin & dp vec 초기화
    for( int n_idx = 1; n_idx<= N ; n_idx++){
        scanf("%d", &(coin_vec.at(n_idx)) );
        // 동전이 구하는 K 값보다 크면 버린다.
        if ( coin_vec.at(n_idx) > K ) continue;
        dp.at(coin_vec.at(n_idx)) = 1;
    }
 
    // dp 갱신
    // 모든 동전에 대하여 확인하고 min 으로 값을 갱신한다.
    for ( int dp_idx = 1 ; dp_idx <= K ; dp_idx++){
        for( int n_idx = 1; n_idx <= N ; n_idx++) {
            // 현재 dp 위치에서 코인의 값을 더했을 때, k 이상이면 버린다.
            int next_dp_idx = coin_vec.at(n_idx) + dp_idx;
            if ( K < next_dp_idx ) continue;
 
            // 현재 dp의 위치에서 1 을 더한 값이 index 보다 작으면 교체
            if (dp.at(dp_idx) + 1 < dp.at(next_dp_idx) )
                dp.at(next_dp_idx) = dp.at(dp_idx) + 1 ;
 
        }
    }
 
    printf("%d", dp.at(K) == INF ? -1 : dp.at(K));
 
    return 0;
}
cs



Search