문제 설명
Dynamic Programming의 정석과도 같은 문제 유형 중 하나이다.
주어진 동전의 가치로 목표 가치를 달성하기 위해 필요한 최소의 동전 개수를 계산하기 위해 다이나믹프로그래밍으로 접근해야 한다. 문제에 따라서 완전탐색 등의 다른 방식으로도 접근이 가능하나, 해당문제는 조건에 의해 시간복잡도를 계산해서 제한 시간 안에 계산이 가능한지 확인한 후, 완전탐색으로는 불가능하다는 점을 인식해야 한다.
문제 풀이 시도 및 문제점 고찰
- 첫 번째 아이디어: 목표 가치(ex. 15)까지의 크기를 갖는 배열을 생성한 후, 0부터 해당 목표 index까지의 최소 동전 개수를 하나씩 계산해서 배열을 채워나가는 방식을 구상하였으나, 주어진 동전의 가치들로 동전의 개수를 배수한 것인지, 다른 것들과 덧셈한 것인지 알 수 없었음. 어떤 것이 최소인지 구분할 방법이 존재하지 않는다는 문제가 발생하였다.
- 두 번째 아이디어: 주어진 동전 가치들의 배수를 계속 계산해 나가면서 최소의 동전 개수로 배열을 업데이트하는 방식. 모든 조합을 고려해야하기 때문에 시간초과가 발생할 가능성이 농후했다.
발생한 문제점 및 고찰
- dp_array 를 위한 점화식을 구상하지 못했음: 다이나믹 프로그래밍의 핵심은 최선의 결과를 도출하기 위해 특정 점화식을 기준으로 max or min으로 값을 비교한 뒤 array를 업데이트 해 나가는 방식이다. 허나 본인은 이 문제를 해결하기 위한 점화식을 구상하지 못했다.
- 본인은 가능한 방법을 조사하기 위한 그래프탐색과 비슷한 방식으로 문제를 해결하려고 시도했던 점이 큰 문제였다.
- 문제를 이해했으면 필요한 알고리즘 및 문제풀이 방식이 무엇인지 빠르게 가닥을 잡고 해결하고자 하는 자세가 부족했다.
- "배수 및 조합"을 해결해야하는데, 문제에서는 동전의 조합을 출력하는 것이 아닌 최소 동전의 개수만 필요하다 하였으므로, 개수가 최소가 되는 경우만 기록하면 되는 것에 집중하면 된다.
- 배열에서 이미 이전의 최소 개수들을 저장하고 있다면, 다음 idx로 넘어갈 때 해당 idx 값 + 주어진 동전의 가치 부분의 값은 +1만 해주면 된다는 것이 이 문제풀이의 핵심이다. 즉, input[i] <= j <= K 에 대해, dp_array[j - input[i]] + 1 로 dp_array를 계속 업데이트 해 나간다면, 내부에서 동전의 조합은 어떻게 이루어지는지 모르지만, 항상 해당 위치에는 최소값으로 업데이트가 될 수 있다.
- 아래 첨부한 사진을 바탕으로 예시를 들어보겠다. input은 오름차순으로 정렬되어 있지 않아도 된다. min으로 비교하면 된다. input[i] 의 배수로 달성가능한 수를 반복적으로 기록해나간다. 그 다음 더 큰 input으로 더 적은 개수로 해당 가치를 달성이 가능하다면, 업데이트한다. 이 방식은 최소개수를 보장한다.
- input이 2, 3, 5, 6 이고 달성하고자 하는 가치가 12라면, i=0부터 input에 대해 반복하고, j는 dp_array를 업데이트하기위해 K까지 반복한다고 한다면, dp[j] = min(dp[j], dp[j-input[i] + 1)의 방식으로 항상 최소의 개수를 보장할 수 있게 된다.
문제 풀이
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
class Solver{
private:
const static int K_MAX = 10000;
int N, K, answer=0;
int input[K_MAX+1];
int dp_array[K_MAX+1];
public:
Solver(){}
void Init();
void DP_Init();
void Solve();
void Print();
~Solver(){}
};
void Solver::Init(){
cin >> N >> K;
int in;
for(int i=0; i<N; i++){
cin >> in;
if(in <= K) input[i] = in;
else input[i] = 0;
}
fill(dp_array, dp_array+(K+1), INT_MAX-1);
//sort(input, input+N);
//for(int j=0; j<N; j++)
//cout << input[j] << " ";
return;
}
void Solver::DP_Init(){
for(int i=0; i<N; i++)
dp_array[input[i]] = 1;
//dp_array[K] = -1;
return;
}
void Solver::Solve(){
Solver::DP_Init();
for(int i=0; i<N; i++){
for(int j=input[i]+1; j<=K; j++){
dp_array[j] = min(dp_array[j], dp_array[j-input[i]] + 1);
}
}
/*
for(int j=1; j<=K; j++)
cout << dp_array[j] << " ";
*/
return;
}
void Solver::Print(){
answer = dp_array[K];
if(answer == INT_MAX-1) answer = -1;
cout << answer << '\n';
return;
}
int main(){
Solver solver;
solver.Init();
solver.Solve();
solver.Print();
return 0;
}