먼저 문제에 오타가 있다.
문제에는 초콜릿을 1명 제외하고 1, 3, 5개씩 분배할 수 있다고 나와있지만
실제로는 1, 3, 5개가 아니라 1, 2, 5개로 하고 문제를 풀어야 한다.
이 문제는 살짝 시각을 바꿔서 바라볼 필요가 있다.
먼저 선택된 1명을 제외하고 분배해서 모두 다 같은 개수를 갖도록 하는것은
선택된 1명의 초콜릿을 빼앗아서 모두 같은 개수를 갖게 하는 것과
같은 횟수의 절차를 거치며
n-1명에게 각각 초콜릿을 분배하는 것은 n-1번의 연산을 필요로 하지만
1명으로부터 초콜릿을 뺏는 것은 1번의 연산을 필요로 하기 때문에
동일한 문제를 더 효율적으로 해결할 수 있다.
정리하자면 문제를 다음과 같이 재정의할 수 있을 것이다.
한번에 선택된 1명으로부터 1, 2, 5개의 초콜릿을 빼앗을 수 있다고 할 때
최소 몇번만에 모두 같은 개수의 초콜릿을 가지도록 할 수 있을까?
첫번쨰 사람부터 순서대로 N1개 N2개 N3개 .... N(n-1)개, Nn개를 가지고 있고 이 집합을 N이라 할 때 가장 적게 가지고 있는 사람의 초콜릿 개수를 min(N) 이라고 하자
그리고 나서 집합 N의 각 element에 min(N)을 빼서 min(N)과의 차를 값으로 갖는
집합 N'을 만들어보자.
이제 남은 것은 집합 N의 각 element에서 1,2,5씩 뺄셈을 하면된다. 가장 적은 횟수로!
가장 적은 뺄셈 횟수를 구하는 법은 욕심쟁이 기법을 이용하면 된다.
m번째 사람의 초콜릿 개수 Nm을 min(N)로 만들기 위한 뺄셈 횟수를
계산하는 식은 다음과 같다.
(Nm-min(N)) / 5 + ((Nm-min(N)) % 5 / 2) + ((Nm-min(N)) % 5 % 2)
다만 이 경우는 목표 개수를 min(N)으로 잡고 각 element를 뺄셈하는 경우인데
어떤 경우는 목표 개수를 min(N) - α 로 하는 것이 더 적은 횟수로 도달하기도 한다.
그렇다고 목표 개수를 0부터 min(N) 까지 다 해보기엔 너무 비효율적이다.
그러므로 규칙성을 이용해야한다.
목표개수가 min(N)인 경우는
a) min(N) - 5k 인 경우보다 횟수가 k번 적다. (5를 k번 뺌)
b) min(N) - 5k + 1인 경우보다 횟수가 k+1번 적다. ( -5 * k, -1 )
c) min(N) - 5k + 2인 경우보다 횟수가 k+1번 적다. ( -5 * k, -2 )
d) min(N) - 5k + 3인 경우보다 횟수가 k+2번 적다. ( -5 * k, - 2, - 1)
e) min(N) - 5k + 4인 경우보다 횟수가 k+2번 적다. ( -5 * k, - 2 * 2 )
이후는 앞의 경우에서 동일한 개수를 만족한 상태에서 추가적인 뺄셈을 하는 것이므로 의미가 없다. ( 최소 횟수를 구하는 문제)
그러므로 총 5가지의 목표 개수 T = [ t1, t2, t3, t4, t5 ]를 정하고
집합 N을 순회하면서 5가지 경우의 횟수 C = [ c1, c2 ,c3 ,c4 ,c5] 합산한다.
i : 1~n
j : 1~5
Cj = ∑∑ (Ni - Tj) / 5 + ((Ni - Tj) % 5 / 2) + ((Ni - Tj) % 5 % 2)
min(C)가 정답이다!