[백준] 2839 설탕 배달(그리디) - Python

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

2839번: 설탕 배달

 

n = int(input())
five = n // 5 # 최대 5kg 몇 개 쓸 수 있는지
check =True
while check: 
    if n % 5 == 0: # 만약 5kg으로만 옮길 수 있으면 5로 나눴을 때 몫 출력
        print(five)
        break
    else:
        while True: # 아닐 때
            temp = n - (five * 5) 
            if temp % 3 == 0: # 5kg 최대로 쓰고 3kg으로 나머지 옮길 수 있을 때
                three = temp // 3 # 3kg 몇 개 써야하는지
                print(three + five)
                check = False
                break
            five -= 1 # 안될 시 5kg 하나 빼고 다시 while문
            if five < 0: # 못 옮기는 경우
                check = False
                print(-1)
                break

 

- 접근방식: 처음에 최대 공약수, 최소공배수 이런식으로 접근해보다가 최대 5kg으로 다 옮길 수 있는 경우 부터 5kg 하나 덜 쓰는 경우, 5kg 두 개 덜쓰는 경우 이런식으로 접근.

- 느낀점: 그리디 풀 때는 처음에는 직관적으로 생각해서, 그 다음 범위를 줄여가는 식으로 접근해보자