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
동전 0 문제는 그리디 알고리즘을 이용한 문제입니다.
그리디 알고리즘이란?
간단히 말해서 하나의 트리에서 최종 출력값이 가장 큰 것이 아닌 지금 바라보고 있는 상태에서 가장 큰것을 가져가면서 트리를 타고 내려가게 되는 알고리즘입니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int n, nu, num[10];
int temp = 0;
scanf("%d %d", &n, &nu);
for (int i = 0; i < n; i++) {
scanf("%d", &num[i]);
}
for (int i = n-1; i >= 0; i--) {
if (nu < num[i])
continue;
temp += nu / num[i];
nu%=num[i];
}
printf("%d", temp);
}
이에 따라 이번 문제에서는 여려개의 값을 받아 반복하기 위해 배열을 써줍니다.
배열안에 동전들의 단위가 주어지고 다시 배열을 거꾸로 돌리면서 계산하고자 하는 값보다 단위값이 더 크면 무시하고 반복합니다.
반복하면서 만약 단위가 나누려는 값보다 작아지면 if 문에 의해 걸러지고 있던 반복문의 연산이 시작됩니다.
temp 에 값을 나눈값의 몫을 더 해주고 다시 nu (나눠야할 값)에는 아까의 수식에서의 나머지를 넣어줍니다. 이 것을 반복해서 결과가 출력이 됩니다.
예를 들어서 입력값이 4200 원일땐 5000원까지는 4200 보다 크기 때문에 if 문에서 continue 가 되고 1000원이 됐을때 1000원으로 4200을 나눠줍니다. 몫을 저장하게되면 1000원 4개가 사용됐다고 표현할 수 있고 나머지 값 200원이 남게됩니다.
다시 그럼 200원보다 작아질때까지 포문이 돌고 200원보다 작아지면 아까와 같이 200/100 의 몫 2가 들어가고 나머지가 없기 때문에 temp 에는 6개 라는 값이 들어가게 됩니다.
'C,C++' 카테고리의 다른 글
구조체 선언과 이용, 초기화 (0) | 2021.11.11 |
---|---|
2167번 2차원 배열의 합 (0) | 2021.07.21 |
10773번 제로 C (0) | 2021.06.15 |
풀어보려 시도 해본 문제들 (백준 : 1009번, 14647번, 2136번) (0) | 2021.06.09 |
백준 20492번 세금 (0) | 2021.06.09 |