[그리디] 이코테 (파이썬) 큰 수의 법칙

[문제]

'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다.

 

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.

 

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자.

 

이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 

 

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 인 46이 된다.

 

...
... 생략
...

 

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

 

[입력 조건]

1. 첫째 줄에 N(2 <= N <= 1,000), M(2 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며,

 

     각 자연수는 공백으로 구분한다.

 

2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000이하의 수로 주어진다.

 

3. 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

[출력 조건]

첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

<입력 예시>
5 8 3
2 4 5 4 6
<출력 예시>
46

 

[내 풀이]

n, m, k = map(int, input().split())
x = list(map(int, input().split()))
result = 0

x.sort()
while True :
  for i in range(k) :
    if m == 0 :
      break
    result += x[n-1]
    m -= 1
  if m == 0 :
    break
  result += x[n-2]
  m -= 1

print(result)

 

공백으로 구분하여 n과 m과 k 변수에 정수형 값을 각각 할당하고, 공백으로 구분하여 N개의 수를 x에 할당한다.

 

또한 문제에서 요구하는 총 누적된 값을 출력하기 위해 result 변수를 선언한다.

 

x에서 가장 큰 수를 구하기 위해 정렬하고, 반복문 내에서는 k번 반복하여 가장 큰 수를 누적한 후 m 값을 1 감소시킨다.

 

특정한 인덱스의 수가 연속해서 K번까지 더해지면 result 값에 두번째로 큰 수를 누적한다.

 

위와 같은 방식을 반복적으로 수행하고 m이 0이라면 반복문을 빠져나와 출력한다. 

 

[답안 예시 provided by 이코테]

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

x.sort()
first = x[n - 1]
second = x[n - 2]

count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first
result += (m-count) * second

print(result)

 

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저