그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 "현재 상황에서의 최적해를 선택하는 방식"이다. 백트래킹을 통해 추가적인 점검을 하지 않고, 현재 선택지 이외에는 검증을 하지 않는다. 하지만 그 해가 항상 최적해라는 보장을 할 수 없다는 한계가 존재한다. 위와 같은 최소 가중치 문제에서, 그리디 알고리즘을 적용하면 7과 10중에 7을 선택하고, 12와 15중에 12를 선택하여 7 + 12 = 19의 가중치를 해로 갖게 된다. 그러나 그림을 보면 알 수 있듯이 실제 최소 가중치는 10 -> 5를 선택하는 15이다. 그리디 알고리즘을 적용했을 때, 매 선택마다 부분 최적해는 구했지만, 전체 최적해를 구하지 못한 것이다. 따라서 그리디 알고리즘은 항상 최적해를 보장하지 못한다고 할 수 있다..

접근 방법 상근이는 최대한 적은 봉지를 들고 가려고 한다. 가장 적은 수의 봉지를 들고 가려면, 가능한 한 5kg의 봉지를 많이, 3kg의 봉지를 적게 구성해야 한다. 정답 코드 import sys n = int(sys.stdin.readline()) flag = 0 for i in range((n // 3) + 1): three = 3 * i five = (n - three) / 5 if five == int(five): print(int(i + five)) flag = 1 break if flag == 0: print(-1) 코드 설명 3kg 봉지의 수가 0개인 경우 -> 1개인 경우 -> .... -> n//3개인 경우 까지 for문을 반복한다. 각 경우에 five 변수는 n에서 three를 뺀 것..