[백준] 12982 공 포장하기 2

12982번: 공 포장하기 2

문제 요약

k개의 종류를 가진 공이 존재한다.

종류마다 공의 갯수는 각각 다르다.

이 공들을 박스에 담을 것이며 박스는 다음 두가지 방식으로 최대 k개의 공을 담을 수 있다.

1. 박스 안의 모든 공의 종류가 다르다.

2. 박스 안의 모든 공의 종류가 같다.

 

최소한의 박스로 공을 전부 담아라.

 

풀이 아이디어

 

먼저 입력 받을 때 같은 종류로 k개를 상자에 담을 수 있다면, 담고 본다.

즉 k개로 나눈 몫 만큼을 결과에 미리 추가해 놓고, k개로 나눈 나머지 값을 입력값으로 사용한다.

 

그 다음 입력값을 오름차순으로 정렬한 후

순회하며 

i번째 까지 1번으로 담는 방법 (오름차순 정렬임으로 i번째 입력값이 박스의 갯수다.) 

+

i+1번째 부터 2번으로 담는 방법( k - 1 - i 가 박스의 갯수다.)

의 최소값을 구한다.

 

위 두개를 더해서 출력하면 된다.

 

 

시행착오

 

 

1번과 2번을 적절히 번갈아 사용해야 풀리는 것 같아서

같은 높이를 가진 공끼리 계산하여 1번과 2번중 최적의 방법을 사용해서 풀었으나

 

k개로 몫을 미리 계산해주고 나면 

n만큼을 1번 방법으로 계산하고 남은 부분을 2번 방법으로 계산하는 방식 밖에 나오지 않는 다는 것을

어림짐작했고, 그대로 풀었더니 정답이였다.

 

이 부분에 대해 이해는 가나 증명하기는 꽤 까다로운 것 같다.

 

 

최적화 하기

 

본 풀이 방식은 O(NlogN)임으로 

더 빠를려면 정렬없이 풀어야 하는데

아마 없을 것 같다.