2839 Sugar Delivery (설탕배달) with Greedy Algorithm

2023-02-14

 

0. Background

I'd like to review through what greedy algorithm is and how to apply it to problem solving.

 

1. Greedy Algorithm

The definition of greedy algorithm is to choose the best option on each stage to get the answer. It does not give you the ultimate answer but it does give you the almost ultimate and optimal answer.

The core of greedy algorithm is to set the definition of what the best option is in a problem.

 

2. Examples

2-1. 11047_Coin

Inputs are N, the number of coin, and K, the value of money.

Get the smalles amount of coin required to meet the value of money

 

Input

10 4200
1
10
50
100
500
1000
5000
10000
50000

 

Output

6

 

2-2. Answer code

n, k = list(map(int, input().split()))
values = []
cnt = 0

for _ in range(n):
    values.append(int(input()))

values.reverse()

for value in values:
    if value > k:
        continue

    quotient = int(k / value)
    k = k % value
    cnt = cnt + quotient

    if k ==0:
        break

print(cnt)

 

2-3. Code Explanation

Try dividing K by coin one by one with ascending order.
Add all quotien into cnt
If K is 0, stop and print cnt
In this problem, the best option was the biggest value of coin

 

3. Code and Explanation

3-1. Problem

Sang-geun is working at sugar factory as a delivery person.

 

2-2. Answer code

kg = int(input())
cnt = 0

while(True):
    if kg%5 == 0:
        cnt = cnt + int(kg/5)
        break
    kg = kg - 3
    if(kg < 0):
        cnt = -1
        break
    cnt = cnt + 1

print(cnt)

 

2-3. Code Explanation

I tried dividing kg by 5 first and by 3 later only one time, it could not give the right answer when getting 11 for the input.
So, I used while statement that stops when kg can be divided by 5, which was the key point to solve this problem.