[그리디] 이코테. 큰 수의 법칙

이코테 : 이것이 취업을 위한 코딩테스트다 책의 예제문제 풀이

문제

배열의 수들을 m번 합해서 가장 큰 수를 만들어야 한다. 다만, 같은 수가 연속으로 k번을 초과해서 더해질 수 없다.
예를 들어 [2,4,5,4,6] 배열에, m = 8, k = 3 이라면 6+6+6+5+6+6+6+5 = 46 이 답이 된다.
인덱스가 다르면 수가 같아도 별도의 횟수로 센다.

문제 조건

1<= n,m,k <= 10000
k <= m

코드

# n,m,k = map(int, input().split())
# lst = [map(int, input().split()) for _ in n]

n,m,k = 5,8,3
lst = [2,4,5,4,6]
lst.sort(reverse=True)

big = 0
first = lst[0]
second = lst[1]

while True:
    for _ in range(k):
        if m == 0:
            break
        big += first
        m -= 1

    if m == 0:
        break
    big += second
    m -= 1

print(big)

핵심

가장 중요한 건, 제일 큰 수 두 개만 번갈아 k개씩 더해주다 m개가 되면 멈추면 된다.

제일 큰 수를 k번 더해주다가, 두번째로 큰 수를 한 번 끼워서 더해주다가 m개가 합해지면 멈춘다. (F+F+F+ S + F+F+F + S...)

나머지 숫자는 필요없다.
if문의 조건을 반복문의 어느 지점에 위치시켜야하는지 연습하기 좋은 문제다.

 

발전

반복제거가 가능하다. 가장 큰 두 수들이 어떤 규칙으로 합해지는 지를 들여다 보아야 한다.

만약 first = 6, second = 5, m=8, k=3 이라면,

    tot = 6+6+6+5+6+6+6+5 =  f+f+f+s + f+f+f+s

    => (k+1)의 사이클, first는 (사이클*k만큼 등장), s는 m-(f등장횟수)

만약 first = 6, second = 5, m=4, k=2 이라면,

   tot = 6+6+5+6 = f+f+s + f

   => first는 (사이클*k + 1res) 만큼 등장 => res 필요

 

즉, first 숫자는 m을 (k+1)만큼 나눈 몫 x 한 사이클당 최대등장횟수 k  만큼 등장한다. 그리고 딱 떨어지지 않는 숫자 동안은 무조건 first 숫자로 더해줘야하기 때문에 m을 (k+1)로 나눈 나머지에 횟수만큼 first 로 합해준다. 

따라서, (first 곱하기 cycle 곱하기 k) + (first 곱하기 res) 가 된다.

이제 남은 횟수만큼은 second 를 더해줘야 한다. 따라서 (second 곱하기 (m - first를 합해준 수)) 를 더해주면, 답이 된다. (사실상, second 곱하기 cycle 와 같다.)  

 

big = 0
first = lst[0]
second = lst[1]

res = m % (k+1)
cycle = m // (k+1)

f_sum = first*k*(cycle) + first*res
s_sum = second*(m-(cycle*k)-res)
print(f_sum+s_sum)