[Beakjoon Online Judge] 11047- 동전 0(C++)

I 문제 소개

---

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

II 문제 풀이

---

사실 너무 간단해서 뭐라고 붙일 문제는 아니다.

다만 앞으로 탐욕법과 관련된 문제를 풀어보려해서 가장 기초적인 문제를 찾아 풀어보았다.

 

문제만 놓고 보았을 때 N을 10 이하로 해서 굳이 동적할당 필요 없이 A[10]의 배열을 만들어도 되고 동전의 가치도 오름차순으로 알아서 주어지기 때문에 신경 써야하는 부분이 얼마 없다.

 

0. 초기 환경 설정

---

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	int N, K;
	vector<int> A;
	int i, temp, answer;
	
    return 0;
}

A[10]의 배열로 만들어도 되지만 그러면 너무 문제가 단순해지기에 N이 정해져있지 않다고 생각하고 일부러 vector를 이용해 풀려고 한다.

 

1. 입력 받기

---

cin >> N >> K;
	
for(i=0;i<N;i++)
{
	cin >> temp;
	A.push_back(temp);
}

코딩을 생으로 처음 시작했을 때 부딪혔던 난관이 정해지지 않은 여러개의 입력을 받는 것이었다.

사실 할 말이 없어서 그냥 적어봤다.

N이랑 K는 한번씩 받기 때문에 제일 위에 적어주었고 N의 크기만큼 받아야하는 A는 반복문으로 입력을 받는다.

다만 주의해야할 점은 A는 배열이 아니라 벡터이기 때문에 push_back을 하지 않고 cin >> A[i] 처럼 접근해버리면 크기가 할당되지 않은 메모리에 접근하는 것이라서 오류가 난다는 점이다.

 

2. 탐욕법

---

앞에서 이 문제는 탐욕법으로 푸는 문제라고 했다.

탐욕법이 뭔데? 라고 한다면 일상생활에서 우리가 현금으로 결제하는 것을 생각하면 편하다.

(영어로는 그리디 알고리즘 :Greedy Algorithm 이라고도 한다.)

 

우리가 세종대왕 3장, 율곡이이 2장, 퇴계이황 10장을 전부 가지고 있다고 했을 때 💰10,000원을 계산하려면 보통 세종대왕 1장을 주지 율곡이이 2장이나 퇴계이황 10장을 주지는 않는다.

 

가장 이득인 것부터 고르는 계산법, 가장 최선을 고르는 계산법이 탐욕법이다.

 

이 문제에 빗대자면, 가장 화폐가치가 높은 지폐/동전부터 탐색하면서 낼 수 있는한 최대로 내는 것이다.

 

코드로 풀면 다음과 같다.

answer = 0;
	
for(i=A.size()-1;i>=0;i--)
{
	temp = K/A[i];
	answer += temp;
	K = K - (temp*A[i]);
}

A[A.size()]는 존재하지 않으므로 주의하자. 별다른 연산을 하지 않는 이상 벡터의 끝은 A[A.size()-1]이다.

 

원래 나누어 떨어지는지 검사하거나 버림 등의 계산을 해야하겠지만, int의 특성이 나누면 자동 버림이기 때문에 그것을 이용해 짰다.

 

3. 최종

---

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	int N, K;
	vector<int> A;
	int i, temp, answer;
	
	cin >> N >> K;
	for(i=0;i<N;i++)
	{
		cin >> temp;
		A.push_back(temp);
	}
	
	answer = 0;
	for(i=A.size()-1;i>=0;i--)
	{
		temp = K/A[i];
		answer += temp;
		K = K - (temp*A[i]);
	}
	
	cout << answer;
	return 0;
}

최종 코드다. 간단해서 딱히 더 덧붙일 말은 없다.

 

 

 

III 느낀점

---

사실 문제 난이도가 어렵거나 복잡하지 않고 정말 간단한 문제였다고 할 수 있다.

다만 탐욕법을 공부해보려는 입장에서, 어떤 것인지 감을 잡게 해준다는 점에서 문제를 골라 풀어보았다.

그리디 알고리즘은 보통 탐색 / 정렬 / 비교 / 선택을 거쳐야한다고 하는데, 이 문제는 그럴 것 없이 문제에 조건(오름차순 입력 등)을 걸어서 편하게 접근할 수 있었다.

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 11047번 동전0 C++

BOJ 11047번 동전0 C++

백준 11047번 동전0 C++