[알고리즘] Greedy - 큰 수의 법칙 ( java )

[알고리즘] Greedy - 큰 수의 법칙 ( java )

---

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

 

입력조건

• 첫째 줄에 N(배열의 크기), M(숫자가 더해지는 횟수), K의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력조건

• 첫째 줄에 큰 수의 법칙을 따라 더해진 답을 출력한다.

 

내 코드

import java.util.*;

class Main {
  public static void main(String[] args) {
  
        Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int m=scan.nextInt();
		int k=scan.nextInt();

		Integer[] arr=new Integer[n];
		int answer=0;

		for(int i=0;i<n;i++){
			arr[i]=scan.nextInt();
		}

		Arrays.sort(arr,Collections.reverseOrder());

		if(arr[0]==arr[1]){
			answer=arr[0]*m;
		} else {
			while(true){
				for(int j=0;j<k;j++){
					answer+=arr[0];
					m--;
					if(m==0)
						break;
				}
				answer+=arr[1];
				m--;
				if(m==0)
						break;
			}
		}
		System.out.println(answer);

  }
  
}

 

더 나은 해답 ( 반복되는 수열에 대해서 파악 )

import java.util.*;

class Main {
  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int k = scan.nextInt();

		Integer[] arr=new Integer[n];
		int answer = 0;

		for(int i=0;i<n;i++){
			arr[i] = scan.nextInt();
		}

		Arrays.sort(arr,Collections.reverseOrder());
		
		int tmp = (arr[0]*k) +arr[1];
		int x = m/(k+1);
		answer=x*tmp;
		m=m-x*(k+1);

		for(int i=m;i>0;i--){
			answer+=arr[0];
		}

		System.out.println(answer);

  }
  
}