반응형 그리디 썸네일형 리스트형 [BOJ 2437] 저울 [문제] : https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net [개념] - 그리디 (Greedy) 알고리즘 [풀이] 아이디어만 떠올린다면 생각보다 쉬운 문제이다. N개의 추가 주어졌을 때, 추들을 이용하여 측정할 수 없는 무게 중 가장 작은 무게를 구하는 것이다. 첫 번째로, 측정할 수 있는 무게들을 모두 구하는 것은 당연히 풀이의 의도가 아니라는 것을 알 수 있어야 한다. 완전 탐색으로 구한다고 한다면 추의 개수가 최대 1000개이므로 경우의 수가 최대.. [BOJ 8980] 택배 [문제] : https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net [필요 개념] - 그리디 (Greedy) 알고리즘 [풀이] 문제 난이도 치고 (풀이일 기준 Gold 4) 생각보다 풀이 방법이 쉽게 떠오르지 않은 문제였다. 처음에는 보내는 마을을 오름차순으로 정렬한 후, 현재 트럭에 있는 박스 개수를 계속 비교하면서 더 채울 수 있으면 채우고, 내릴 수 있으면 내리는 방식으로 하였으나 당연히 WA를 받았다. 다음과 같은 반례가 있.. 이전 1 다음