탐욕 알고리즘 :: 백준 :: 캔디캔디 :: 2879

캔디캔디

https://www.acmicpc.net/problem/2878

아.. 어렵다

처음에 생각한 풀이법은

50 10

1

10

6

2

5

3

4

7

8

9

이런 입력이 주어졌다고 할 때, list[]에 저장한 뒤 sort를 하고 이분탐색으로 

left			mid						right
1	2	3	4	5	6	7	8	9	10

50 -> 16

				left		mid			right
0	0	0	0	1	2	3	4	5	6

16 -> 1

							left	mid	right
0	0	0	0	0	0	0	1	2	3

위의 그림과 같이 왼쪽 범위의 숫자들을 0으로, 오른 쪽 범위의 숫자들은 list[mid]의 숫자만큼 빼주며 이분탐색을 진행하려 했으나

숫자가 작을 때, 과연 어느 숫자를 줄여줘야 할지...

이 경우에는 3을 1 줄이는 것이 최선이라는 것을 딱 알 수 있지만 다른 복잡한 경우는 어떻게 처리해야 할지 고민하다 결국 해결하지 못했다.

오래 고민을 하다 결국 해답을 봐버렸다..

구글 없었으면 아마 컴퓨터 공부 못했을 것 같다.

[풀이방법]

S : 친구들이 원하는 사탕 개수의 합

M : 가지고 있는 사탕의 수 라고 할때

K : 친구들이 받지 못하는 candy의 개수(S-M)

라 할때,

합이 일정할 때 요소들의 수가 같아야 최소다(예를 들어 1^2+7^2 > 4^2+4^2 인 것 처럼..)라는 사실을 바탕으로

친구들에게 사탕을 K개만큼 부족하게 잘 배분해야(...?!풀어쓰기 어렵다)

  -> 원하는 양 만큼의 사탕을 받지 못하는 친구들의 사탕의 개수가 최대한 비슷하도록! 배분해야함!!