joseph0528 코딩 블로그

(한별이가 나오는 몇 안 되는 희귀한 문제이다.) 이 문제는 한가지 관찰만 하면 쉽게 풀 수 있다. 그 관찰은 바로 많아도 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있다는 것이다. 만약 a 용기에 0ml가 있고 b 용기에 1ml가 있고 총용량이 10ml 일 때 a와 b를 합치면 1+5=6ml가 된다. 그리고 c 용기에 2ml가 있다고 하고 앞에서 구한 6ml 용기와 c를 더하면 6+2+5로 10ml를 넘어간다. 이걸 하나의 식으로 나열하면 a+b+c+10/2+10/2 가 된다. 즉 a, b, c 모두 0ml 이어도 10/2 가 두 번 더해져 10으로 꽉 찬 용기가 되기 때문에 최대 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있는 것이다. 맨 처음에 정렬을 해준 뒤 C[i]가 X와 같다면 혼자서도 꽉..