Search
Duplicate

동전 0

주차
16
문제번호
11047
언어
C++
티어
실버
유형
그리디
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사