[ 이것이 코딩 테스트다 with Python ] 그리디 - 큰 수의 법칙 (Python)

이 글은 이것이 취업을 위한 코딩테스트다 책을 기반으로 쓰여진 글입니다.
출처 : 이것이 취업을 위한 코딩테스트다

 

---

문제 

여기서 큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과할 수는 없음

 

입력 조건

첫째 줄에 N(2<=N<=1000), M(1<=M<=10000), K(1<=K<=10000)의 자연수가 주어지며 각 자연수는 공백으로 구분

둘째줄에 N개의 자연수가 주어짐. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1이상 10000이하의 수로 주어짐

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

 

출력 조건

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

 

입력 예시

5 8 3

2 4 5 4 6 

 

출력 예시

46 

 

* 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5  =  46

---

알고리즘

1. 둘째줄의 리스트를 소팅해 내림 차순 정렬함

2. 가장 큰 수를 K번 더하고 두번째로 큰 수를 1 번 더하고 가장 큰 수를 K번 더함

3 수를 더할 때 마다 m을 1씩 감소 시키고, m이 0이 아닐때 까지 반복

3. 더한 값 출력

 

필요 함수 정리

내림차순 소팅

• sort.(reverse=True)
  • 형식 : 리스트.sort(reverse = True)
  • sort 함수에 reverse 파라미터를 사용해 내림차순으로 정렬

 

while 문

• while
  
  • 형식 : while <조건문>:
  • 조건이 참인 동안 계속 반복

 

 

 

 

 

내 소스 코드

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

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

answer = 0

while m!=0 :
    for i in range(k) :
        answer += first
        m -= 1

    answer += second
    m -= 1

print(answer)

 

결과 

 

책 소스 코드

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
data = list(map(int, input().split()))

data.sort() # 입력 받은 수들 정렬하기
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기

print(result) # 최종 답안 출력

* 반복되는 수열 파악

더해지는 수들은 가장 큰 수 k번 + 두번째로 큰 수 1번 의 조합으로 반복됨

따라서 총 M을 (k+1)으로 나눈 몫에 k를 곱하면 조합이 반복되며 큰 수가 더해지는 횟수

그 값에 M을 (k+1)을 나눈 나머지를 더하면 조합 이외에 큰 수가 더해지는 횟수

 

* 결과값에 더하기

결과값에 큰 수 횟수 * 큰 수를 더하고

총 횟수에서 큰 수 횟수를 빼고 두번째로 큰 수와 곱해 더함

결과값 출력