큰 수의 법칙

문제 : 

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징

 

예 :

2, 4, 5, 4, 6으로 이루어진 경우 M=8, K=3이라면 6+6+6+5+6+6+6+5=46

 

=> 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과 출력하시오.

 

입력 조건 :

• 첫째 줄에 N(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

 

---

코드

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

# 2가지 뿐
data.sort(reverse=True) # 내림차순 정렬
first = data[0] # 가장 큰 수
second = data[1] # 두 번째로 큰 수

# 가장 큰 수가 나온 횟수
cnt = k*int((m/(k+1))) + m%(k+1)

result = cnt*first + (m-cnt)*second
print(result)

 

코드 설명

단순하게 구현하면 M의 값이 커질 경우 시간 초과 판정을 받을 수 있다.

따라서, 반복되는 수열에 대해서 파악해야 한다.

최대값을 구하기 위해서는 (가장 큰 수*k)+(두 번째로 큰 수*1) 이라는 수열이 반복됨을 알 수 있다.

(=> 위의 예시의 경우 {6,6,6,5}라는 수열이 반복됨)

 

그러므로 내림차순 정렬을 통해 가장 큰 수와 두 번째로 큰 수를 각각 구하고,

가장 큰 수가 나온 횟수를 k * int(m/(k+1)) + m%(k+1) 이라는 식을 통해 구하고,

이를 통해 최종 결과값을 구할 수 있다.

 

---

 

++

한 번에 생각해내지 못한 방법.. 분발하자