백준 2294번: 동전 2

 

문제 링크 : https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

 알고리즘 

 

문제는 DP문제인데 아무것도 모를때 완탐으로 풀어서 시간초과가 난적이있다 , ,

 

아래 블로그를 참고하고 풀었당

참고한 블로그 : https://jaemin8852.tistory.com/163

 

 

 

 코드 

 

#include<iostream>
#include<algorithm>
 
using namespace std;
int arr[100001];
int k, n, dp[101];
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> n >> k;
 
    //최댓값 으로 배열 초기화
    for (int i = 1; i <= k; i++) {
        arr[i] = 10001;
    }
 
    for (int i = 1; i <= n; i++) {
        cin >> dp[i];
        for (int j = dp[i]; j <= k; j++) {
            arr[j] = min(arr[j], arr[j - dp[i]] + 1);
        }
    }
    //불가능한 경우
    if (arr[k] == 10001) cout << -1;
 
 
    else cout << arr[k];
 
}