Memo
로직 설명
•
오름차순 정렬이 되어있으므로, 뒤에서 부터 조사하며 최대한 K의 값을 감소시키도록 동전을 고릅니다.
코드 설명
for (int i = N - 1 ; K != 0 && i >= 0 ; i--)
{
if (A[i] <= K)
{
ans += (K / A[i]);
K %= A[i];
}
}
C++
복사
•
로직 설명에서 말한 부분입니다.
•
A[i]가 K보다 작거나 같다는 것은, 그 동전을 사용할 수 있다는 뜻이기 때문에 최대한 사용합니다.
Code
제출 날짜
@4/14/2021
메모리
2016 KB
시간
0 ms
#include <iostream>
#include <vector>
int N, K, ans;
std::vector<int> A;
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;
A.resize(N);
for (int i = 0 ; i < N ; i++)
std::cin >> A[i];
}
void solve()
{
for (int i = N - 1 ; K != 0 && i >= 0 ; i--)
{
if (A[i] <= K)
{
ans += (K / A[i]);
K %= A[i];
}
}
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사