[Greedy] 동전0 - 백준

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

11047번: 동전 0

 

반례와 많이 씨름을 했던 문제이다. 

 

다음 문제는 동전을 이용하여 주어진 수를 구축할 때 가장 최소가 되게 하는 문제로 굉장히 단순한 유형에 속했지만

반례를 대응하지 못해 한동안 고생했던 문제였다. 

 

논리는 다음과 같다. 

4200원을 만들기 위해

1000원, 300원 1원이 주어졌다고 하면

 

Greedy의 논리를 빌려 가장 큰 1000원이 갯수를 가장 적게 차지할 것이라는 가정하에

1000원을 기점으로 점차 갯수를 줄여나가며 minimum 갯수를 찾는 방법이다. 

 

예를 들어

1000원이 4번 쓰인다면

남은 잔액은 200원이므로 

300, 1원으로 200원을 만들기 위해서는

1원을 200번 써야 한다.

 

이러한 논리를 사용하여 가장 전체 동전 수가 적은 경우를 찾는다.

 

 

이 경우는 1000원을 3번 쓰고 300원 4번 쓴 총 7이 가장 적은 경우다. 

 

이를 처음에 구현한 코드는 다음과 같은데 86%에서 실패가 떴다. 

N, K = [int(x) for x in input().split()]

num_list = []
for _ in range(N) :
    num_list.append(int(input()))

new_list = [ n for n in num_list if n <= K ]
first = new_list[len(new_list)-1]

criteria = K//first
now = K; so_far = float('Inf')


while criteria > 0 :
    now -= first*criteria
    accum = criteria
    for i in range(len(new_list)-2,-1,-1) :
        q = now//new_list[i]
        accum += q
        now -= q*new_list[i]
    if accum < so_far :
        so_far = accum
    criteria -= 1
    now = K
print(so_far)

 

이후 반례를 찾아보니

참고 https://y-e-un28.tistory.com/9

 

1 500

1

이 경우 즉, 동전이 1개만 주어진 경우는 내 알고리즘은 갯수를 적합하게 찾을 수 없었다.

 

고로 특수 경우의 조건을 추가해주어 문제를 겨우 풀었다...

 

반례 조건이 없이 바로 문제를 풀 수 있는 조건이 있을까?

N, K = [int(x) for x in input().split()]

num_list = []
for _ in range(N) :
    num_list.append(int(input()))

new_list = [ n for n in num_list if n <= K ]
first = new_list[len(new_list)-1]

criteria = K//first
now = K; so_far = float('Inf')

if len(new_list) == 1 :
    print(criteria)
else :
    while criteria > 0 :
        now -= first*criteria
        accum = criteria
        for i in range(len(new_list)-2,-1,-1) :
            q = now//new_list[i]
            accum += q
            now -= q*new_list[i]
        if accum < so_far :
            so_far = accum
        criteria -= 1
        now = K
    print(so_far)

이 분의 경우 매우 간단하게 구현하였는데 참고하자

https://deepwelloper.tistory.com/entry/BOJ-11047-%EB%8F%99%EC%A0%84-0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%92%80%EC%9D%B4

 

최대한 단순하게 구현하는 연습을 자꾸 해보자...