[코테] 그리디 문제풀기 - 큰 수의 법칙

Day3

그리디 문제풀기 - 큰 수의 법칙 (2019 국가 교육 기관 코딩 테스트 기출 / 난이도 하)

 

<문제>

배열 안 N개의 숫자들 중에서 숫자들을 골라 M번을 더하여 가장 큰 수를 출력해야한다. 그런데 특정 인덱스 숫자가 연속 K번을 초과하여 더해질 수 없다. 

 

<조건>

첫째 줄 : N, M, K 자연수 입력. 공백 구분

둘째 줄 : N개의 자연수. 공백 구분

K는 항상 M보다 작거나 같다. 

 

큰 수의 법칙 풀이

import sys

n, m, k = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))

numbers.sort()
a = numbers[-1] #가장 큰 수
b = numbers[-2] #두 번째로 큰 수

answer = 0
cnt = 0

#숫자들을 m번 더함
for i in range(0, m):

  #배열의 특정 인덱스 숫자가 k번 초과하지 않은 경우
  if cnt < k:
    print("cnt:" + str(cnt)) #디버깅
    answer += a #첫 번째로 큰 수를 더함
    cnt += 1
    print(answer) #디버깅

  #k번 초과한 경우
  else: 
    print("else cnt:" + str(cnt)) #디버깅
    answer += b #두 번째로 큰 수를 더함
    cnt = 0
    print(answer) #디버깅
  
print(answer) #정답

하나의 숫자를 k번만 연속해서 더할 수 있으므로 가장 큰 수를 k번 반복하여 더하고 두 번째로 큰 수를 한 번 더해주면 최종적으로 가장 큰 수를 구할 수 있다. 예를 들어, n=4, m=7, k=3이고 4 6 3 8의 배열이 주어지면 a=8, b=6이 되고, 8+8+8+6+8+8+8 =54가 된다.

+ while문과 break를 활용하여 코딩할 수도 있다. 또는 가장 큰 수가 더해지는 횟수를 찾아서 두 번째로 큰 수가 더해지는 횟수를 m과 k를 활용해 각각 구하는 방식으로 코딩할 수도 있다.