협동력 점수
문제
N명의 학생을 K개의 그룹으로 나누고자 한다. 각 학생은 협동력 점수를 가지고 있으며, 단 하나의 그룹에만 속할 수 있다. 모든 학생은 반드시 각자 특정한 하나의 그룹에 배치된다.
모든 학생에 대한 그룹 배치가 끝나고 나면, 각 그룹의 전투력을 계산할 수 있다. 이때 특정한 그룹의 전투력은 그룹에 포함된 각 학생에 대하여 (해당 그룹에 속한 구성원 수 X 해당 학생의 협동력 점수)을 계산하여 모두 더한 값이다. 어떤 학생의 협동력 점수는 음수(-)일 수 있으며, 결과적으로 특정한 그룹의 전투력은 음수가 될 수도 있다.
이때, N명의 학생으로 K개의 그룹을 구성하는 모든 경우를 고려했을 때, 가장 전투력이 높은 그룹과 전투력이 낮은 그룹의 전투력 차이의 최솟값을 구하여라. 단, 모든 K개의 그룹에 최소한 1명의 학생은 배치되어야 한다.
예를 들어 N=4명의 학생들의 협동력 점수가 다음의 표와 같으며, 그룹의 수 K=2라고 하자.
| 학생 번호 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 협동력 점수 | -1 | 0 | 3 | -2 |
가장 먼저, 다음과 같이 두 그룹을 결성했다고 가정하자.
| 그룹 번호 | 1 | 2 |
|---|---|---|
| 학생 번호 구성 | [1, 2] | [3, 4] |
이때 전투력은 다음과 같이 계산되므로, 두 그룹의 전투력 차이는 4이다.
(1) 1번 그룹의 전투력: -2 = 2 * (-1) + 2 * 0 (2) 2번 그룹의 전투력: 2 = 2 * 3 + 2 * (-2)
혹은 다음과 같이 두 그룹을 결성했다고 가정하자.
| 그룹 번호 | 1 | 2 |
|---|---|---|
| 학생 번호 구성 | [2] | [1, 3, 4] |
이때 전투력은 다음과 같이 계산되므로, 두 그룹의 전투력 차이는 0이다.
(1) 1번 그룹의 전투력: 0 = 1 * 0 (2) 2번 그룹의 전투력: 0 = 3 * (-1) + 3 * 3 + 3 * (-2)
따라서, 현재 입력 예시에서의 최적의 해는 0이다.
입출력 예시
예시 1
입력
4, 2, [-1, 0, 3, -2]
출력
0
예시 2
입력
5, 4, [2, 1, 1, 2, 3]
출력
2
입력 조건
가장 먼저 학생의 수 N이 자연수로 주어진다. N은 2 이상 7 이하의 자연수다.
이어서 그룹의 수 K가 자연수로 주어진다. K는 2 이상 N 이하의 자연수다.
이후에 각 학생의 협동력 점수 정보가 담긴 배열 arr가 주어진다. 각 학생들의 협동력 점수는 -10 이상 10 이하의 정수이다.
출력 조건
N명의 학생으로 K개의 그룹을 구성하는 모든 경우를 고려했을 때, 가장 전투력이 높은 그룹과 전투력이 낮은 그룹의 전투력 차이의 최솟값을 반환한다.
요구사항
- solution(N, K, arr) 함수를 만들고 답을 반환해야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 20개이고, 그 가운데 5개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 20개를 전부 통과해야 해결입니다.
예시
공개 케이스 5개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 20개를 전부 통과해야 해결입니다.
4, 2, [-1, 0, 3, -2]
0
5, 4, [2, 1, 1, 2, 3]
2
6, 3, [-8, 4, -2, 11, 0, -4]
3
3, 2, [5, 7, -8]
7
3, 2, [0, -6, 3]
6
참고 사항
풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.
원본에서 모의고사 5회 3번입니다.
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 5개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.