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

다양한 수로 이루어진 배열 : N

숫자가 더해지는 횟수 : M

연속해서 K 번 초과해서 더해질수 없음 (단, 배열에서 서로 다른 인덱스에 해당하는 같은 숫자는 서로 다른것으로 간주)

 

입력조건

• 첫째줄에 N, M, K의 자연수가 주어지고, 각 자연수는 공백으로 구분
• 둘째줄에 N 개의 자연수가 주어진다
• 입력으로 주어지는 K는 항상 M 보다 작거나같다

출력조건

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

 

입력예시

5 8 3

2 4 5 4 6

출력예시

46

 

 

파이썬 표현법 알아둘것들

• A를 B로 나눴을때 몫 구하는 표현  :  int(A/B)  아니면  A // B
• N개의 수를 공백으로 구분하여 입력받기 : data = list(map(int, input().split()))
• n, m, k 를 공백으로 구분하여 입력받기 : n, m ,k = map(int, input().split())

 

접근하기

1. sort()를 이용해서 제일 큰 값과 두번째로 큰 값을 구한다

2. 수를 더할때마다 m -1 해주고, m이 0이될때까지 반복한다

3. while문 안에 제일 큰 값은 k 번 만큼, 두번째로 큰값은 1번 더하게 구성한다

# 리스트 sort(reverse=True) : 내림차순 정렬
# 가장 큰 수 k번 더하고, 두번째 큰수 1번 더하고, 가장큰수 K번 더함
# 수를 더할때마다 m 을 -1 하고, m 이 0이 아닐때까지 반복

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

l.sort(reverse=True)
first = l[0]
second = l[1]

result = 0
while m!=0:
    for i in range(k):  # k=3 이라면, first값이 총 3번(0~2) 더해진다
        result += first
        m -= 1

    result += second
    m -= 1

print(result)

 

책 해설 코드_ 창의력버전

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

l.sort() # 오름차순 정렬
first = l[n-1]
second = l[n-2]

count1 = (m // (k+1)) * k
count1 += m % (k+1)

count2 = (m // (k+1))

result = (count1 * first) + (count2 * second)