그리디 : 큰수의 법칙

✨"이것이 취업을 위한 코딩테스트다" 라는 책을 보며 코테문제 푼것을 정리해보고자 한다!

그리디 알고리즘 : 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘

모든 알고리즘이 그렇겠지만 그리디 알고리즘은 한마디로 가장 효율적으로 결과값을 연산할 수 있는 알고리즘이다.

대표적으로 큰수의 법칙 문제가 있다.

🎈 큰수의 법칙
첫 줄에 n , m, k의 자연수가 둘째 줄에는 자연수가 공백으로 구분되어 있게 주어진다.
n은 배열의 크기, m은 숫자가 더해지는 횟수, k는 연속해서 더해질 수 있는 횟수이다.
이 조건을 만족시켜 가장큰 수를 출력하세요!

n=5, m=8, k=3이고, [2,4,5,4,6] 으로 이루어진 배열이 있을 때
6+6+6+5+6+6+6+5 =46이 된다.

✨이 문제의 핵심은 구조를 파악하는 것

1. 가장 큰 두수만 더하면 되는 구조.
2. 가장 큰수가더해진 횟수와 두번째로 큰수가 더해진 횟수를 세어 더하면 된다

• n은 배열의 크기, m은 숫자가 더해지는 횟수, k는 연속해서 더해질 수 있는 횟수

🥕 큰 수가 더해지는 횟수 = m/(k+1) + m%(k+1)

: [6+6+6+5]+[6+6+6+5] -> 반복되는 구조를 파악하여 구함

🥕 두번쨰 큰 수가 더해지는 횟수= (m- 큰 수가 더해지는 횟수)

📌코드

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

data.sort()

first = data[n-1]
second = data[n-2]

count = int(m/(k+1)*k + m%(k+1))

result = first*count + (m-count)*second
print(result)

📈금융 개발 블로그 : https://quantpro.co.kr/