#문제
11047번: 동전 0
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
#접근방법
가장 높은 가치를 가진 동전부터 몇 개가 필요한지 구하면 되는 그리드 알고리즘을 사용하였다.
반응형
#풀이
#include <stdio.h>
int arr[10];
int main(){
int n,k,ans = 0;
int sum = 0;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
for(int i=n-1;i>=1;i--){
int cnt = (k-sum)/arr[i];
ans += cnt;
sum += cnt*arr[i];
}
ans += k-sum;
printf("%d",ans);
return 0;
}
문제에서 A1 = 1이라고 명시가 되어있기 때문에 무조건 가지고있는 동전으로 k원을 맞출 수 있다.
따라서 제일 가치가 높은 동전부터 순서대로 몇 개의 동전이 필요한지 구하면 되는 그리드 알고리즘을 사용할 수 있다.
n,k를 입력받고 n개만큼 arr[i]배열에 동전의 가치를 저장해준다.
n-1부터 1까지 반복문을 돌리면서 cnt = (k-sum)/arr[i]를 구해준다.
cnt의 의미는 해당 동전을 k금액이 넘어가지 않도록 최대한으로 쓴 동전의 개수이다.
ans에 cnt를 더해주고 sum에 cnt*arr[i]을 더해준다.
반복문이 끝나게 되면 ans에 k-sum을 더해주는데 이는 k금액을 맞추기 위한 1원 동전의 개수이다.
ans를 출력하면 정답이다.
#성능
#정리
A1 = 1이라는 조건을 보고 그리드 알고리즘을 생각하는 것,
이를 구현할 수 있는 구현력이 있으면 풀 수 있는 문제였다.
'하루 한 문제' 카테고리의 다른 글
[백준] 17219번 : 비밀번호 찾기 [C/C++] (0) | 2022.06.22 |
---|---|
[백준] 11399번 : ATM [C/C++] (0) | 2022.06.21 |
[백준] 1764번 : 듣보잡 [C/C++] (0) | 2022.06.19 |
[백준] 11723번 : 집합 [C/C++] (0) | 2022.06.18 |
[백준] 1676번 : 팩토리얼 0의 개수 [C/C++] (0) | 2022.06.17 |