시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 904 | 248 | 187 | 27.180% |
주띵이는 오프라인 카드 게임 하프 스톤을 좋아하는 평범한 대학생이다. 주띵이가 자주 방문하는 게임용품 전문점인 '카드 몬스터'에서는 개점 3주년을 기념해 카드 팩 이벤트를 진행하고 있다. 이벤트에 참여한 사람은 사장이 만든 규칙을 만족하면 한 번에 많은 카드를 저렴하게 구매할 수 있다.
예를 들어서 N=10이고 M=3인 경우를 가정해보자. 각 카드의 식별 번호가 차례로 10, 9, 7, 7, 9, 8, 8, 8, 2, 1 이라고 한다면, 아래와 같은 방법들로 구매할 수도 있다.
그림1. 카드 팩을 한 장으로 구성한 경우의 예시
그림 2. 카드 팩을 두 장으로 구성한 경우의 예시
그림 3. 구매할 수 없는 경우의 예시
개점 이벤트로 인해 각 카드 팩을 구성하는 카드 수에 상관없이 항상 가격이 일정하므로, 주띵이는 최대한 많은 카드를 카드 팩으로 구성하려고 한다. 하지만 한 번 카드 팩을 구성한 이후에 수정하는 것은 가게 주인이 좋아하지 않으므로, 미리 가장 이득이 되는 방법을 설계한 후 구성하려고 한다. 주띵이를 도와주자. 주띵이가 각 카드 팩에 구성할 수 있는 최대의 카드 수는 몇 장인가?
첫 줄에는 두 개의 자연수 N과 M이 공백으로 구분되어 주어진다. N은 상점에 진열된 카드의 수이며 M은 주띵이가 구매해야 할 카드 팩의 수다. 이후 두 번째 줄에는 총 N개의 나열된 카드에 대한 자연수 식별 번호가 입력으로 주어진다. 가장 왼쪽에 나열된 카드부터 오른쪽에 나열된 카드까지 실제 위치와 같은 순서로 식별 번호가 주어지며, 각 식별 번호는 공백으로 구분되어 있다.
각 카드의 식별번호는 1 이상 50만 이하의 자연수이다.
이벤트의 규칙을 모두 만족하면서 주띵이가 하나의 카드 팩에 구성할 수 있는 카드의 최대 수량을 한 줄에 출력한다.
10 1 5 2 5 3 4 1 3 1 2 1
5
10 1 4 4 4 5 4 4 3 4 5 4
3
10 3 10 9 7 7 9 8 8 8 2 1
3
3번 예제는 Small 에서는 나오지 않는다.
University > 아주대학교 > 2018 Ajou Programming Contest > Division 1 D번