[이코테/JAVA] Greedy - 큰 수의 법칙

문제

 

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

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더할 수는 없다.

 

입력
배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 숫자를 최대로 더할 수 있는 횟수 K

 

출력
큰 수의 법칙에 따라 더해진 답

 

예시

• 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M=8, K=3이라고 가정하자. 특정한 인덱스의 수를 연속해서 3번까지 더할 수 있으므로 큰 수의 법칙에 따라 결과는 6+6+6+5+6+6+6+5=46이 된다. 
• 다른 예시로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M=7, K=2라고 가정하면, 결과는 4+4+4+4+4+4+4=28이 된다. (다른 인덱스의 4이기 때문에 계속 4를 더할 수 있다)

풀이

문제를 단순하게 만들면, 더해서 최대한 큰 수를 만드는 것이다. 최대한 큰 수를 만들기 위해서는 가장 큰 수를 최대한 많이 더하는 것이 좋다. 따라서

1. 오름차순으로 배열을 정렬하고 배열의 끝을 가져와서 a변수에 저장.

2. a를 k번만큼 더한다. 이때, 더할 때마다 count값을 더하고 m이 넘지않는지 검사를 해준다. 

3. 그 다음 큰 수를 b에 저장하고 count값을 더하고 m을 넘지않으면 b를 한번만 더해준다.

(한번만 더해주는 이유는 a를 최대한 많이 더해줘야하기때문)

4.  최종 값을 출력한다.

코드

package Week08;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class NDB_큰수의법칙 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		int num[] = new int[n];
		
		for(int i=0;i<n;i++) {
			num[i]=Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(num);	// 오름차순 정렬
		
		int a = num[n-1];	// 가장 큰 수 
		int b = num[n-2];	// 그다음 큰 수
		
		int ans=0;
		int count=0;
		
		while(count<=m) {
			
			for(int i=0;i<k;i++) {
				count++;			// 더한 횟수 더해주기
				if(count>m) break;	// m번을 초과했을 경우
				else {
					ans+=a;
				}
			}
			count++;
			if(count>m) break;
			else ans+=b;
			
		}
			
		
		
		System.out.println(ans);
		
	}

}