[백준] 2293번: 동전 1 (C++)

 

입력 받은 코인의 금액으로 코인 여러 개를 사용하여

목표 코인 금액을 맞출 수 있는 경우를 찾는 문제

물론 브루트 포스로도 풀 수 있겠지만

이 문제는 제한 시간이 0.5초로

다이나믹 프로그래밍으로 풀어야한다

 

dp[0]은 모든 코인이 0개가 사용되므로

dp[0] = 1로 설정한다

 

새로 갱신되는 dp 값은

새로운 코인 단위를 사용하기 전의 dp 값과 

새로운 코인 단위의 dp 값을 합하면 

새롭게 dp가 갱신된다

 

 

문제의 예시 경우를 살펴본다

 

1원, 2원, 5원을 사용하여 10원을 구성하는 예시이다

1원을 사용하는 경우

1원부터 10원까지 구성할 수 있는 경우는 모두 1가지

 

2원을 사용하는 경우

1원 1가지, 2원 2가지(1+1, 2),

3원의 경우 1원만 사용해서 3원을 구성하는 경우와

2원을 1원과 2원을 사용해서 구성하는 경우를 합한다

이와 같은 방식을 반복하여 문제를 해결한다

 

// baekjoon 2293

#include<iostream>
#include<algorithm>
using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

//int MAX = 100001;

int main(){
    init();
    
    int N, K;
    cin >> N >> K;
    
    int coin[100001];
    int dp[10001];
    
    for(int i = 1; i <= N; i++){
        cin >> coin[i];
    }
    //sort(coin, coin + N);
    
    dp[0] = 1;
    
    for(int i = 1; i <= N; i++){
        for(int j = coin[i]; j <= K; j++){
            dp[j] += dp[j - coin[i]];
        }
    }
    
    cout << dp[K];
    
    return 0;
}

입력과 출력을 제외하면

위 문제의 핵심 코드는 단 3줄이다

하지만 이 3줄을 어떻게 구성하느냐가

예제를 직접 풀어보면서 문제를 분석하는 과정인 듯하다

 

참고 사이트

[백준] 2293번. 동전 1 (velog.io)