그리디 (Greedy) (2) - 실전문제 3.2) 큰 수의 법칙

문제)
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만든다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M=8, K=3 이라면 주어진 규칙대로 가장 큰 수를 만드는 방법은 6+6+6+5+6+6+6+5가 되고 결과는 46이 된다.

입력 조건)
1. 첫째 줄에 N (2≤N≤1,000), M (1≤M≤10,000), K (1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000이하의 수로 주어진다.
3. 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건)
첫째 줄에 주어진 큰 수의 법칙에 따라 더해진 답을 출력한다.

입력 예시)
5 8 3
2 4 5 4 6

출력 예시)
46

이 문제를 읽고 그리디 알고리즘을 떠올렸다. 그 근거로는 가장 큰 수를 주어진 규칙에 따라 더해야 결과도 가장 큰 수가 나오기 때문이다. 문제 해결을 위해서 리스트로 입력 받은 N개의 수들을 내림차순 정렬 하는 것과 반복문을 구현하지 않고 합을 구하는 규칙을 찾아서 간단하게 구현하는 것이 포인트였다. 내림차순 정렬은

리스트이름.sort(reverse=True) 를 통해서 진행했다. 

주어진 규칙 아래에서 가장 큰 수를 만들기 위해서는 아래의 규칙을 적용했다.

• 내림차순 정렬로 얻은 리스트의 0번째 인덱스에 해당하는 수 (가장 큰 수) 를 K번 더한다.
• 같은 인덱스의 수를 K번 초과해서 더할 수 없기 때문에 다음으로는 리스트의 1번째 인덱스에 해당하는 수 (두번째 큰 수)를 1번 더한다.
• 이를 계속 반복하여 M번 더한 합계를 출력한다.

 

---

소스코드

https://github.com/Engineering-Student-An/algorithm_python/blob/master/greedy/%EC%8B%A4%EC%A0%84%EB%AC%B8%EC%A0%9C%203-2%20%ED%81%B0%20%EC%88%98%EC%9D%98%20%EB%B2%95%EC%B9%99.py