기출 : 2019 국가 교육기관 코딩 테스트
다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만든다.
배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수는 없다.
예를 들어
[2, 4, 5, 6] 배열이고,
M=8, K=3 이다.
이럴 경우 6+6+6+5+6+6+6+5 가 최대 합이다.
단, 서로 다른 인덱스에 해당하는 수가 같은 경우에는 서로 다른 것으로 간주한다.
예를 들어
[3, 4, 3, 4] 배열이고,
M=7, K=2이다.
두 위치에 있는 4는 다른 4이므로,
4+4+4+4+4+4+4가 가능하다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과를 출력하자.
입력 조건
첫째 줄: (2<=N<=1,000), M (1<=M<=10,000, K(1<=K<=10,000)의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.
둘째 줄: N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 각각의 자연수는 1 이상 10,000이하이ㅏㄷ.
- K는 M보다 작거나 같다.
출력조건
첫째 줄: 큰 수의 법칙에 따라 더해진 답을 출력한다.
입력 예시
5 8 3
2 4 5 4 6
출력 예시
46
1차 접근
우선 배열 내에서 가장 큰 수의 인덱스를 찾는다.
가장 큰 수를 K번 더한다.
두번째로 큰 수를 구한다.
두번째로 큰 수를 1번 더한다.
2번 줄과 4번 줄을 반복한다.
각 덧셈마다 덧셈 카운트를 증가시킨다. 덧셈 카운트가 M이 되면 덧셈을 그만한다.
만약 배열 내에 가장 큰 수가 두 위치에 있더라도, 위 알고리즘은 올바른 답을 찾아낼 수 있다.
가장 큰 수를 찾는 알고리즘을 올바르게 짜면 말이다.
2차 접근
같은 수가 두개 이상일 때 처리하는 코드가 길어질 것 같아서 다른 방법을 생각했다.
우선 배열을 크기 순으로 정렬한다.
그런다음 마지막 인덱스의 수를 K번 더하고,
뒤에서 두번째 인덱스의 수를 1번 더한다.
3,4를 반복한다.
배열을 어떻게 크기 순으로 정렬할지가 관건이다.
정렬 알고리즘은 다양한데,
따로 정렬 알고리즘을 쓰지 않고 python 내장함수 sorted()를 써서 정렬할 수 있다.
답안 보충
덧셈 카운트를 미리 구할 수도 있다.
K번, 1번, K번, 1번이 반복되므로,
덧셈 식을 살펴보면 K+1 씩 반복된다.
즉, 수열이 반복되는 횟수는 M // K+1 이다. 즉, 몫이다. 물론 나머지 횟수만큼도 가장 큰수가 더해질 것이다.
따라서 가장 큰수가 더해지는 횟수는
(M // K+1) * K + (M % K+1)
두번째로 큰 수가 더해지는 횟수는 전체 덧셈 횟수 M에서 가장 큰 수가 더해지는 횟수를 빼면되다.