[그리디 13] 동전 0

최적의 일반화

정답 비율 : 51.828%

1. 문제 설명하기.

(1) 문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

(2) 입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

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

• ☑ 이 부분을 제대로 이해하지 못하여 중간에 애를 먹었다.

(3) 출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

가장 좋은 것부터 고려 (가장 큰 수부터) 하는 점을 통하여 탐욕법으로 풀이하는 그리디 문제임을 알 수 있다.

2. 문제 해결하기.

Step 1. N,K를 입력 받고 arr를 내림차순으로 정렬한다. 그리고 result를 1로 지정한다.
Step 2. N만큼 반복문을 돌리고 차례로 K가 각각의 arr보다 크거나 같은지 확인한다. 조건을 만족한다면 result에 N을 K로 나눈 몫만큼 더해주고, K는 그 나머지로 재할당한다.
Step 3. Step 2의 조건을 만족하지 않는다면 다시 반복문으로 올라간다.
Step 4. result를 출력한다.

# 미니 예제 1 : N=10, K=4200

N=10
K=4200
arr=[1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
arr.sort(reverse=True)
result=0

for idx in range(N):
    if K>=arr[idx]:
        result+=K//arr[idx]
        K-=arr[idx]*(K//arr[idx])
    continue

print(result)

# 미니 예제 2 : N=10, K=4790

N=10
K=4790
arr=[1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
arr.sort(reverse=True)
result=0

for idx in range(N):
    if K>=arr[idx]:
        result+=K//arr[idx]
        K-=arr[idx]*(K//arr[idx])
    continue

print(result)

위의 코드는 문제를 제대로 이해하지 못하여 잘못 풀이하였다. 결국 런타임 에러 (ValueError)가 떴다.

• ☑ arr 부분은 언제든지 변경될 수 있는 부분이다. 위의 조건 (Ai는 Ai-1의 배수)만 지킨다면 문제가 없다.

# 최적의 일반화

N, K=map(int, input().split())
# arr=[1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
arr_list=list()
result=0

for i in range(N):
    arr_list.append(int(input()))

for idx in range(N):
    arr_list.sort(reverse=True)
    result+=K//arr_list[idx]
    K=K%arr_list[idx]

print(result)

조건을 하나 더 걸어줘서 더 빨리 끝나게 코드를 짰다. (K가 arr_list보다 작은 경우는 반복문으로 다시 올라가기.)

Step 1. N,K를 입력 받고 result를 1로 지정한다.
Step 2. arr_list를 입력 받는다.
Step 3. N만큼 반복문을 돌리고 arr_list를 내림차순으로 정렬한다. 그리고 K가 각각의 arr_list보다 크거나 같은지 확인한다. 조건을 만족한다면 result에 N을 K로 나눈 몫만큼 더해주고, K는 그 나머지로 재할당한다.
Step 4. Step 3의 조건을 만족하지 않는다면 다시 반복문으로 올라간다.
Step 5. result를 출력한다.

N, K=map(int, input().split())
# arr=[1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
arr_list=list()
result=0

// arr_list 입력 받기.
for i in range(N):
    arr_list.append(int(input()))

// 내림차순으로 정렬하고, 조건에 맞으면 result와 K 구하기.
for idx in range(N):
    arr_list.sort(reverse=True)
    if K>=arr_list[idx]:
        result+=K//arr_list[idx]
        K=K%arr_list[idx]
    continue

print(result)