Problem info
| Title | Codeforces Round 975 |
| Division | Div.2 |
| Problem | C. Cards Partition |
Try
| # | Verdict | Time |
|---|---|---|
| 1 | WA on 3 | +126 |
| 2 | WA on 4 | +140 |
| 3 | Accept | -1 |
풀이방식
모든 카드를 사용해야 하며 같은 카드가 한 덱에 2개 이상 존재하면 안된다.
이 조건으로 인해 덱의 개수는 최소 $max(a_i)$개가 된다.
그렇기 때문에 $max(a_i) * l$이 가능한 가장 큰 $l$을 찾으면 된다.
여기서 2가지 Case로 나누어 볼 수 있는데
$max(a_i)$를 p,
$max(a_i)$를 제외한 나머지 값들의 합을 $q$라고 가정할 때
- $max(a_i)$개의 deck을 만든다.
- $p > q/(l-1)$
- $max(a_i)$보다 큰 deck을 만든다.
- $p < q/(l-1)$
1번의 경우 $k$를 $q$의 개수를 채우는 데에 사용하면 되고,
2번의 경우 $k$를 $p$의 개수를 채우는 데에 사용하면 된다.
이때 주의해야할 점은 $k$의 개수가 모자라서 $p * l$개의 카드를 채우지 못한다면 어떤 방식을 사용해도 덱을 완성할 수 없다.
Example
Let $p = 5$ and $q = 13$ and $k = 0$
If $l = 3$, it can only $k = 0$
You must use all cards.
$3*5=15$, but $p+q=16$ there is one card left.
Therefore, you can’t make a deck with a size of 3.
Solution
- 현재 가지고 있는 card의 종류 중 max값($p$)과 max값을 제외한 나머지 값의 합($q$)을 구한다.
- $i$를 최대값(n)부터 2까지 (2가 불가능하다면 답은 1이다) 반복하면서 size가 $i$인 deck을 만들 수 있는지 확인한다.
a. 만약 어디서든 $k$를 사용하더라도 답을 구할 수 없으면 계산을 무시하고 다음 size를 확인한다.
b. k를 활용하면서 size가 $l$인 $p$개의 덱을 만들 수 있다면, 정답을 출력하고 다음 testcase로 넘어간다.
c. 불가능하다면 $l$을 1 줄이고 반복한다.
Time complexity: $O(n)$
코드에선 sorting을 하였는데, max값만 가지고 있다면 굳이 필요 없는 부분이다.