https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
c++로 백준 11047번 문제를 풀어보겠다.
문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력 1 복사
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력 1 복사
6
<문제 풀이>
1. N과 K를 입력받는다.
2. N개의 숫자를 입력받아 int 형의 배열에 저장한다.
3. for 반복문을 통해 뒤에서부터 돌며 K와 N을 나눠, 몫은 저장하고 나머지는 다시 K값으로 저장한다.
4. 계산한 최종 count 값을 출력한다.
코드는 다음과 같다.
'C++' 카테고리의 다른 글
| [백준 알고리즘] 3036번 : 링, c++ (0) | 2022.02.17 |
|---|---|
| [백준 알고리즘] 9375번 : 패션왕 신해빈, c++ (0) | 2022.02.16 |
| [백준 알고리즘] 11399번 : ATM, c++ (0) | 2022.02.16 |
| [백준 알고리즘] 11051번 : 이항 계수 2, c++ (0) | 2022.02.15 |
| [백준 알고리즘] 11050번 : 이항 계수 1, c++ (0) | 2022.02.15 |