[백준 BOJ] 11047번 동전 0 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

접근 방법 - 그리디 알고리즘을 응용한 문제

백준의 11047번 문제는 그리디 알고리즘을 응용하여 해결해야 하는 문제이다.

해당 문제는, 입력받은 숫자에 대하여 최소로 필요한 동전의 수를 출력해야 하는 문제이다.

여기서 그리디 알고리즘이란 아래의 정의를 가지고 있다.

- 그리디 알고리즘은 탐욕 알고리즘이라고도 한다.
- 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다.
- 종합적으로 보았을 때는 최적이라는 보장이 절대 없다.

필자는 위 정의를 짚고, 가장 높은 동전의 단위부터 연산을 시작하여 문제를 해결해보았다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 동전의 단위를 저장할 배열 arr를 전역 변수로 선언한다.

이때, 동전의 합에 대하여 유효한 동전 단위들 중 최댓값을 저장할 변수 max를 0으로 초기화하여 선언한다.

(실행시간을 줄이는 데에 필요한 변수이기 때문에 참고하길 바란다.)

 

2) 동전 단위의 개수(n), 동전 합(k), 동전 단위(arr)를 순차적으로 입력받는다.

이때, 오름차순으로 주어지는 동전 단위들 중 k보다 작은 숫자는 순차적으로 max에 저장한다.

 

3) 총 동전의 수를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

4) 반복문을 통해, 큰 동전의 단위부터 시작해 아래의 연산을 수행하도록 한다.

(이때, 위에서 구하였던 max를 통해 유효한 인덱스부터 연산을 취하도록 한다.)

- 해당 동전 단위에 대해 필요한 동전의 개수를 cnt에 최대로 더한다. (k를 현재 arr 배열값으로 나누었을 때의 몫을 cnt에 더한다.)

- 위 연산으로 남은 돈은 k의 값으로 저장한다. (k를 현재 arr 배열값으로 나누었을 때의 나머지를 k에 저장한다.)

=> 위 연산을 계속 수행하다가, k가 0이 되는 순간이 온다면 해당 반복문을 종료한다.

 

5) 최종적으로 저장된 cnt의 값을 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 11047번 코드
int arr[10];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	int max = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] <= k) { max = i; }
	}

	int cnt = 0;
	for (int i = max; i >= 0; i--) {
		cnt += k / arr[i];
		k %= arr[i];
		if (k == 0) { break; }
	}
	cout << cnt << endl;
}

 

제출 결과

(2022.06.30 백준 11047번 문제 제출 결과)