Memo
•
•
갯수의 최대값은 1로 10,000을 만드는 갯수인 10,000 입니다.
•
입력을 오름차순으로 받아야 로직이 정상 동작합니다. (sorting 적용)
나눗셈 연산은 비싸다
•
처음 코드 (4ms)
void solve()
{
size_t ind;
for (size_t i = 0 ; i < n ; i++)
{
ind = coins[i];
for (size_t j = ind; j <= k ; j++)
{
if (dp[j - ind] != _MAX)
dp[j] = std::min(dp[j], dp[j - ind] + 1);
else if (!(j % ind))
dp[j] = j / ind;
}
}
}
C++
복사
•
나머지 연산을 위로 올린 코드 (8ms)
void solve()
{
size_t ind;
for (size_t i = 0 ; i < n ; i++)
{
ind = coins[i];
for (size_t j = ind; j <= k ; j++)
{
if (!(j % ind))
dp[j] = j / ind;
else if (dp[j - ind] != _MAX)
dp[j] = std::min(dp[j], dp[j - ind] + 1);
}
}
}
C++
복사
•
나머지 연산을 없앤 나중 코드 (0ms)
void solve()
{
size_t ind;
for (size_t i = 0 ; i < n ; i++)
{
ind = coins[i];
dp[ind] = 1;
for (size_t j = ind; j <= k ; j++)
if (dp[j - ind] + 1 < dp[j])
dp[j] = dp[j - ind] + 1;
}
}
C++
복사
갯수가 가장 적은 것은, 해당 코인을 가지고 있는 값 자체이기 때문에 먼저
dp[ind] = 1;
로 초기화를 해준 후, 원래 dp에 저장된 값과 비교하여 최소의 값을 찾아갑니다.
따라서 나머지 연산이 필요없게 되므로, 속도는 더 빨라집니다.
Code
제출 날짜
@3/23/2021
메모리
2176 KB
시간
0 ms
#include <iostream>
#include <vector>
#define _MAX 10002
size_t n, k;
std::vector<int> coins;
std::vector<int> dp;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> n >> k;
coins.resize(n);
dp.resize(k + 1, _MAX);
for (size_t i = 0 ; i < n ; i++)
std::cin >> coins[i];
}
void solve()
{
size_t ind;
for (size_t i = 0 ; i < n ; i++)
{
ind = coins[i];
dp[ind] = 1;
for (size_t j = ind; j <= k ; j++)
if (dp[j - ind] + 1 < dp[j])
dp[j] = dp[j - ind] + 1;
}
}
void print_val()
{
if (dp[k] != _MAX)
std::cout << dp[k];
else
std::cout << -1;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사