[알고리즘] 그리디 알고리즘 - 백준 11047 파이썬 문제풀이: 동전 0

백준 11047번 : 그리디 알고리즘 '동전 0' 문제 파이썬 문제풀이

---

 

문제 풀이에 앞서서, 그리디 알고리즘에 대한 설명은 아래에 있습니다. 

참고하시길...!

 

 

2022.12.21 - [백준 알고리즘] - [알고리즘] 그리디 알고리즘

[알고리즘] 그리디 알고리즘

 

 

 

 

 

 

<문제>

 

11047번 문제의 내용은 아래와 같습니다. 

 

 

동전 0 

 

문제

준규가 가지고 있는 동전은 총 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

예제 입력 2 복사

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2 복사

12

---

 

 

 

 

 

<작성한 코드>

 

---

 

 

 

 

 

<코드 풀이>

 

그리디 알고리즘을 적용하면 생각보다 굉장히 쉽게 풀이가 가능합니다. 

 

먼저 첫번째 줄에는 문제에서 주어진 조건에 맞게, 

map 함수를 이용해 N과 K라는 변수에 입력값을 받도록 했습니다. 

 

 

 

 

 

 

 

다음으로 문제에서 주어진 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다.

라는 조건을 지키기 위해서 'coin'이라는 이름의 빈 리스트를 만들고, 동전의 가치를 입력받아 리스트에 추가했습니다. 

또한 K원 만드는데 필요한 동전 개수의 최솟값을 세어주기 위해서 cnt라는 변수도 함께 만들었습니다. 

 

 

 

 

 

 

 

 

그리디 알고리즘 적용)  이제 그리디 알고리즘을 적용해보겠습니다. 

우리는 동전 개수의 최솟값을 출력할 것이기때문에 최대한 높은 가치의 동전을 사용해서  K원을 만들어내야합니다. 

따라서 만들어준 coin 리스트에서 가치가 높은 동전부터 계산하면서 내림차순으로 내려오는 방법을 선택했습니다. 

이를 위해 reversed 함수를 사용해 리스트를 뒤집었습니다. 

 

 

 

그럼 이제 만들어야하는 K원을 높은 가치의 동전부터 시작해서 계산해나가면 됩니다. 

K//i 를 통해 나온 몫은 cnt에 더해주고

K%i 를 통해 나온 나머지는 새롭게 계산을 해줘야하기 때문에

K라는 변수에 다시 할당해주면 문제는 쉽게 해결됩니다. 

 

 

 

 

 

[그리디 알고리즘 정당성 입증]

이런 그리디 알고리즘은 항상 적용 가능한 것은 아닙니다. 

지난 포스팅에서 살펴본 것처럼 그리디 알고리즘의 적용을 위해서는 정당성 입증이 필요합니다. 

 

 

 

본 문제에서 그리디 알백준11고리즘이 적용 가능한 이유는 주어진 동전의 가치가 서로 배수 관계이기 때문입니다. 

즉 낮은 가치의 동전들을 활용하면 그 위의 높은 가치의 동전들을 만들어낼 수 있습니다. 

ex) 500원 = 100원 * 5

 

 

 

하지만 만약 문제가 본 문제와 다르게 동전의 가치가 500원, 400원, 100원으로 주어지고 800원을 만들라고한다면

그리디 알고리즘은 적용이 불가능합니다. 

 

 

 

500원과 400원은 위에 제시한 것처럼 서로 배수관계가 아니기 때문입니다. 

즉 800원을 만들라고 했을때 그리디 알고리즘을 적용한다면 500-100-100-100 으로 총 4회의 값이 나오지만

최적의 해는 4회가 아닌 400-400으로 총 2회입니다. 

 

 

 

따라서 이런 그리디 알고리즘을 적용하기 위해서는 항상 정당성 입증이 필수입니다.