문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
제한 사항
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
문제를 보고 든 생각
이게 동적계획법 문제인가 싶었다.동적계획법 알고리즘에 굉장히 취약하다고 생각해서 백준에 있는 동적계획법 카테고리의 맨 위의 문제를 마주한 것인데전혀 동적계획법 같지 않고 그냥 그리디 알고리즘 같았다.
나의 아이디어
그냥 그리디 알고리즘을 적용하면 될 것 같았다.상근이가 원하는 건 최소의 봉지 개수로 배달을 하는 것이다.그러려면 우선적으로 5kg을 고려해야 하고 어쩔 수 없다면 3kg을 고려해야 한다.그리고 마지막에 5kg과 3kg으로 계산이 안 됐다면 -1을 출력시키도록 했다.
결과
생각보다 괜찮았다.
하지만 이게 왜 동적계획법인지 전혀 이해가 되지 않았다.
내가 아는 동적계획법은 분명 어떤 반복적인 상황에서 계산식을 세워서 풀어야 하는 건데 말이다.
아래는 그리디 알고리즘을 기반으로 작성한 나의 코드이다.
sugar = int(input())
count = 0
while sugar > 0:
if sugar % 5 == 0:
count += sugar // 5
sugar %= 5
else:
sugar -= 3
count += 1
if sugar < 0:
print(-1)
else:
print(count)느낀점
다른 동적계획법 문제를 더 찾아봐야겠다.
생각보다 시시하게 풀려서 글은 작성하지 않으려고 했다.
하지만 내가 그리디 알고리즘에 강한 것도 아니라서 그리디 알고리즘 문제를 금방 풀어냈다는 거에 기분이 좋았다.
물론 내가 특히 강하다고 생각하는 알고리즘은 없다.
잘하는 알고리즘이 생기도록 계속 공부하자.
