[백준] No.2437 - 저울 (C++)

문제

 

www.acmicpc.net/problem/2437

2437번: 저울

 

풀이

 

solved.ac 난이도: Gold3

 

그리디 알고리즘 문제이지만 DP문제에서 많이 본 유형이라 문제 분류를 몰랐다면 DP로 접근했을 듯한 문제였다.

 

해당 문제의 그리디 알고리즘은 다음과 같다.

 

일단 추를 무게의 오름차순으로 정렬했다 가정하자.

지금까지 idx번째의 추까지 사용하여 만들 수 있는 무게들 중 가장 큰 것을 end_num라고 하자.

다음 추 idx+1를 추가적 이용하여 만들 수 있는 무게들은 0,1,2 ~ end_num들에 모두 idx+1의 무게를 더한 것과 같다.

즉, end_num은 end_num +weight_list[idx+1]이 되고 만들 수 있는 무게는 1~end_num+weight_list[idx+1]이다.

 

만약 다음 추의 무게(weight)가 end_num+1 보다 크다면

0,1,2 ~ end_num들에 모두 해당 값을 더해주어도만들 수 있는 무게는 0~end_num에서 끊기고, weight~end_num+weight가 된다.

따라서 이런 경우 정답은 만들 수 있는 최댓값의 다음 값인 end_num+1이다.

 

예를 들어 

1 1 2 2 8의 추가 주어진다면 

 

1 -> end_num: 1

1 -> end_num: 2

2 -> end_num: 4

2 -> end_num: 6

8 -> end_num +1 < 8

 

따라서 답은 end_num+1인 7이다.

 

추가적으로 end_num +1 < weight_list[idx]인 경우가 없을 수도 있기 때문에

이 경우에는 최종 end_num에 +1 한 만들 수 없는 무게의 최솟값이 답이 된다.

 

코드