분류 전체보기 (81) 썸네일형 리스트형 [백준] 2437번 저울 [문제] 무게가 양의 정수인 N개의 저울 추가 주어졌을 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값 구하기. [풀이] Greedy 방식으로 해결할 수 있는 문제로, 각 추를 정렬 후 누적합을 구하면서 해결해 나갈 수 있습니다. 우선, 추의 배열을 w, 누적합의 배열을 acc라고 정의하겠습니다. 무게가 1인 추가 있을 때, acc[i-1] + 1 >= w[i] 일 경우 acc[i-1] ~ acc[i] 사이의 모든 수를 만들 수 있습니다. 만약 저 조건에 해당하지 않는다면 acc[i-1] + 1이 만들수 없는 수 입니다. 그리고 무게가 1인 추가 없다면 당연히 답은 1이겠죠? 문제에 제시된 예제를 통해 설명하도록 하겠습니다. i 0 1 2 3 4 5 6 추(w) 1 1 2 3 6 7 .. 이전 1 ··· 8 9 10 11 다음