문제접근
모든 동전들을 비교해보면서 최소값을 찾을 것이다.
모든 동전들을 비교할때 각각의 코인의 종류로 비교를 하면서 더 최소값인 녀석들 선택하는 방법을 고를 것이다.
예제의 경우 동전이 1 5 12 로 주어져 있고, 15의 가치를 만들어내는 것이 우리의 목표이다.
DP에는 우리가 만들어 하고 싶은 동전의 값을 의미한다.
우선은 1 만으로 15까지 만들어내는 경우를 정리하면 아래와 같다.
그 다음은 1 과 5 로 만들어내는 경우를 생각해 볼 차례이다.
DP[6]을 구하는 경우 우리는 두 가지를 생각해 낼 수 있다. 기존의 DP[6]의 값(1원짜리 6개 사용)과 DP[1] + 1(기존의 1원을 만들어내기 위해 필요한 동전개수 + 5원짜리 1개) 두 방법이 있고 우리는 이 두 녀석 중 최소값을 찾으면 된다.
따라서 1 또는 5 를 사용하여 만들어내는 경우를 정리하면 아래와 같다.
1 5 12 를 이용하여 만들어내면 아래와 같다
마지막 DP[15]의 경우 DP[15-12] + 1 = 3 + 1 = 4로 생각할 수 있지만! 우리는 위에서 우리가 적용해야할 점화식을 구했었다.
따라서 DP[15]가 이미 3으로 더 최소값이기 때문에 DP[15]는 3이 된다.
다음으로 우리는 성립하는 경우가 없다면 -1을 출력을 하게 하고 싶다. 또한 우리는 1원짜리로 만들어 내는 경우를 비교할때 기존에 들어가 있는 DP값이 없기 때문에 초기화를 해줘야한다! 이 두 조건을 동시에 충족시키게 할 방법이 없을까?
결론부터 말을 하면 DP값을 10001로 초기화를 진행한다.
•
가치들의 합의 최대값은 문제의 조건에 의하여 10000까지 가능하다
•
우리가 만약 1원짜리로 10000을 만들기 위해서는 동전 10000개가 필요하다
•
그렇다면 DP값을 다 업데이트 한 후에 최종 DP값이 여전히 10001이라면 업데이트가 되지 않았음을 의미하고, 그 뜻은 우리가 가지고 있는 동전으로는 그 가치를 만들어낼 수 없다는 것을 의미한다.
•
따라서 우리는 이 경우에 -1을 출력하면 된다
여기서 잠깐...!근데 그럼 1원짜리로 1가치를 만들어낼때는 DP[1-1] + 1이 되는데..?
맞다. 우리는 그래서 DP[0]=0으로 초기화를 해두면 1원짜리로 1가치를 만들때(DP[1-1]), 5원짜리로 5가치를 만들때(DP[5-5]) 등을 편하게 구할 수 있게 된다!
//pseudo code
cin >> n,k
dp배열 10001로 초기화
coin배열에 입력받은 동전종류 입력
for (i <= n)
for(j <= k)
dp[j] = min(dp[j], dp[j-coin[i]]+1)
if(dp[k] == 10001)
cout << "-1"
else
cout << dp[k];
C++
복사
놓쳤던 부분
•
최소값 최신화를 위해 min을 사용했었는데
dp[j] = std::min(dp[j], dp[j - coin[i]] + 1);
C++
복사
위와 같은 코드의 경우 dp[j]가 이미 최소값이라도 다시 업데이트를 하기 때문에 불필요한 대입연산의 과정이 생기게 된다. min을 사용하는 것보다 if문으로 처리하는 것이 더 효율적
코드
2176 KB
0 ms
#include <iostream>
#include <vector>
#define MAX 10001
int n,k;
std::vector<int> dp;
std::vector<int> coin;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n >> k;
dp.resize(k + 1, MAX);
dp[0] = 0;
coin.resize(n + 1);
for (int i = 1; i <= n; i++)
std::cin >> coin[i];
}
void print_answer()
{
if (dp[k] == MAX)
std::cout << "-1";
else
std::cout << dp[k];
}
void solution()
{
for (int i = 1; i <= n; i++)
{
for (int j = coin[i]; j <= k; j++)
{
if (dp[j] > dp[j - coin[i]] + 1)
dp[j] = dp[j - coin[i]] + 1;
}
}
}
int main(void)
{
input_setting();
input();
solution();
print_answer();
return (0);
}
C++
복사
