조건
1. 최초에 가지고 있는 식기의 종류와 수를 모르고
2. 가지고 있는 모든 식기세트는 종류별로 동일한 개수를 가지고 있고
3. 모든 손님에게는 동일한 수의 식기세트를 주며
4. 손님이 다녀간 다음 남아있는 식기들이 n개 주어질 때
도둑맞았을 수 있는 가장 적은 수의 식기 수를 출력하는 문제다.
해법
예제 2번을 보면 쉽게 이해가 간다.
남아있는 식기 수 10개. 손님은 3명
1번 2개
3번 3개
5번 4개
100번 1개
조건 3부터 따져보자.
모든 손님에게는 동일한 수의 식기세트를 줘야하므로 손님 세명에게 5번을 1.33개씩 줘야 한다.
당연히 딱 떨어져야 하므로 2로 올림한다. 따라서 5번은 최소 6개를 가지고 있었다.
조건 2를 보면 모든 식기의 수는 동일하므로 1,3,5,100번 모두 최소 6개씩 가지고 있다.
24 - 10 = 14
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
int c[101];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for (int i = 0; i < n; ++i) {
int t;
cin >> t;
c[t]++;
}
int mv = 0, sum = 0;
for (int i = 1; i < 101; ++i)
mv = max(mv, ((c[i] + k - 1)/k)*k);
for (int i = 1; i < 101; ++i)
if (c[i])
sum += mv - c[i];
cout << sum;
return 0;
}
'codeforces > #522 div2' 카테고리의 다른 글
| B. Personalized Cup (0) | 2018.11.19 |
|---|