이것이 코딩 테스트다 with 파이썬 - 큰 수의 법칙

문제

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 방법을 찾으시오. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 단, 서로 다른 인덱세으 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 3,4,3,4,3으로이루어진 배열이 있을 때 M이7, K가2라고 가장하면 두번째 인덱스의 4와 네번째 인덱스의 4를 번갈아가면서 두 번씩 더하는 것이 가능하여 4+4+4+4+4+4+4=28이 가능하다.

 

입력 조건

• 첫째 줄에 N(2 <= N <=1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.

---

코드

import sys
r=sys.stdin.readline
N,M,K=map(int,r().split())
l = list(map(int,r().split()))
l.sort(reverse=True)

first=l[0]
second=l[1]

cnt=(M//(K+1))*K + (M%(K+1))

print((first*cnt)+second*(M-cnt))

 

해설

이 문제는 반복문으로 풀이해도 무방하지만 M 인풋의 범위가 커지는 경우 시간 복잡도 이슈가 발생할 수 있다. 반복문을 이용해 특정 조건 횟수만큼을 지정해 값들을 더해주는 대신에 단순히 M 과 K 를 이용해 가장 큰 값이 몇번 더해지는지를 구해주면 해결이 가능하다.