[이것이코딩테스트다] Greedy / 큰수의 법칙 / python

큰수의 법칙

 

기출: 2019 국가 교육기관 코딩 테스트

​

큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 떄 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

​

Q. 순서대로 2, 4, 5, 4 ,6으로 이루어진 배열이 있을 떄 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 3번 더해질 수 있으므로 큰 수의 법칙에 따른 결과 6 + 6 + 6 + 5 + 6+ 6+ 6+ 5 = 46이됨.

​

​

입력 예시

5 8 3

2 4 5 4 6

​

출력 예시

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보다 작거나 같다.

​

출력 조건

위 문제에서 제시한 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

 

Think Think 🤔

1. 우선 가장큰수를 무조건 가장 많이 더해줘야한다.
2. 가장 큰수를 K번만큼 더하고 두번째 큰수를 한번 더한 후 다시 가장 큰수를 K번만큼 더하는 식으로 반복하면 될 듯 하다.
3. 수의 인덱스로 중복을 검사하므로 가장 큰수가 2개이상일 경우도 상관없다.

 

코드 구현👀