1. 문제설명
사과의 점수가 담긴 1차원 배열 score.,
score의 최고 점수를 나타내는 k,
사과를 팔 수 있는 박스의 용량 m(m개가 되야 팔 수 있음).
(m개의 점수를 담은 사과 박스의 최저 점수) x m x (상자의 개수) = 해당 사과 박스의 최대 이익.
answer = 최대 이익들의 합.
2. 제한사항
● 3 ≤ k ≤ 9
● 3 ≤ m ≤ 10
● 7 ≤ score의 길이 ≤ 1,000,000
● 1 ≤ score[i] ≤ k
● 이익이 발생하지 않는 경우에는 0을 return 해주세요.
3. 입출력 예시
| k |
m |
score |
return |
| 3 |
4 |
[1,2,3,1,2,3,1] |
8 |
| 4 |
3 |
[4,1,2,2,4,4,4,4,1,2,4,2] |
33 |
4. 나의 풀이
- 시간복잡도를 고려하지 않고 직관적으로 풀어봤습니다.
- m은 고정된 값이니 사과 한 박스의 이익을 최대로 나오게 하기 위해서는 해당 사과 박스의 최저 점수가 높으면 됩니다.
- 이익이 발생하지 않는 경우는 score에 남은 사과점수가 m보다 작을 때입니다. 만약 m이 4이고, score의 길이가 3이면, 사과 한 박스도 만들지 못할테니 이익은 0이 됩니다.
public int solution(int k, int m, int[] score)
{
int answer = 0;
//이익이 없을 때
if (score.Length < m)
return 0;
//score 내림차순 정렬.
score = score.OrderByDescending(x => x).ToArray();
//박스를 만들 수 있는 사과점수의 개수.
int num = (score.Length / m) * m;
//최저 점수를 곱해주는 것이니, m개째 사과 점수만 알면 됨.
for (int i = m-1; i < num; i+=m)
{
answer += score[i] * m;
}
return answer;
}
