[CodingTest] 백준 #11047 동전 0

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

11047번: 동전 0

 

내 풀이 - 1

import sys
n,k = map(int,sys.stdin.readline().split())
coin = []
for i in range(n):
    coin.append(int(sys.stdin.readline()))
len = n
count= 0
coin.sort(reverse=True)
#print(coin)

for i in range(n):
    while coin[i]<=k:
        k-=coin[i]
        #print(k)
        count+=1
print(count)

처음에 생각난 풀이방법은 2번의 풀이방법이었지만, 뒷일을 생각하지 않고 현재의 최선의 선택을 해나가는 탐욕법에는 1번의 풀이과정이 더 맞다고 생각하여 위와 같이 풀어보았다.

풀이 방법은, coin을 내림차순으로 정렬한다. 

coin을 순회하면서 coin[i]가 k보다 작은 동안, k에서 coin[i]를 빼준다.

이 풀이는 pypy3만 통과하고 python3은 시간초과가 나온다ㅠ 그래서 처음 생각한 풀이로 다시 제출해보았다.

 

탐욕법을 공부하고 알게 된 것은 2번 풀이가 탐욕법이라는 것이다.

처음에는 탐욕법이 아니라 생각했는데 매순간 최적이 되는 방법을 선택하는 것이므로, 나눌 수 있을 때까지 나눈 후에 곱한 것을 빼주는 것도 탐욕법이었다.

---

 

내 풀이 - 2

import sys
n,k = map(int,sys.stdin.readline().split())
coin = []
for i in range(n):
    coin.append(int(sys.stdin.readline()))
count= 0

i=n-1

for i in range(n):
    if coin[n-i-1]<=k:
        num = k//coin[n-i-1]
        count +=num
        k -= coin[n-i-1]*(num)
print(count)

coin은 동전의 종류를 담는 리스트이다.

coin을 거꾸로 순회하면서, k, 즉 현재 값보다 작은 값이 나타나면

k가 coin의 해당 원소로 몇번 나눠질 수 있는지 확인하고, 최대로 나눠질 수 있는 수와 해당 coin의 값을 곱한 것을 k에서 빼나간다.

 

 

예를 들어, coin이 [1, 5, 1000, 5000, 10000, 20000] 이고 k가 13000이면 20000부터 거꾸로 순회한다.

20000은 13000보다 크므로 조건에 부합하지 않고, 10000은 13000보다 작으므로 조건에 부합한다.

13000이 10000으로 몇번 나눠질 수 있는지 확인하고, 최대로 나눠지는 수와 10000을 곱해 뺴준다. 

즉, 13000은 10000으로 한번 나눠질 수 있으므로, 13000 - 10000*1을 해준다. 

그러면 k는 3000이 된다. 

다시 순회하면, 3000은 5000보다 작으므로 5000은 패스한다.

3000은 1000보다 크므로, 몇번 나눠질 수 있는지 확인한다.

3000//1000은 3이므로 3000-1000*3을 한 값을 k에 넣는다.

그러면 k는 0이 된다.

1000원 3장, 10000원 1장을 사용했으므로 count는 3+1=4가 된다.

따라서 4를 출력한다.