Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[Greedy] 동전0 - 백준 본문

프로그래밍

[Greedy] 동전0 - 백준

yesungcho 2022. 2. 3. 20:55

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

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

 

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

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

 

논리는 다음과 같다. 

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

 

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

 

 

'프로그래밍' 카테고리의 다른 글

[DP] 퇴사2 - 백준  (0) 2022.02.04
[구현] 삼각 달팽이 - 프로그래머스  (0) 2022.02.04
[DP] 평범한 배낭 - 백준  (0) 2022.02.03
[DP] 설탕 배달 - 백준  (0) 2022.02.02
[DP] N으로 표현 - 프로그래머스  (0) 2022.02.02