[그리디] 큰 수의 법칙

1. 사용 알고리즘 

그리디 

 

2. 문제 해결 아이디어

주어진 배열의 값 중 가장 큰 수 2개를 선택해 조건에 맞게 더해주면 가장 큰 수를 만들 수 있다.

 

3. 코드

구현방식) 반복되는 수열을 사용한다. 가장 큰 수를 만들기 위해서는 최대값을 가장 많이 더해줘야 하므로 K값에 따른 반복되는 수열의 크기는 K+1이 된다. 따라서 더해지는 횟수 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 추가로 M이 (K+1)로 나누어 떨어지지 않는 경우가 존재하므로 이때는 M을 (K+1)로 나눈 나머지만큼 최대값이 추가로 더해진다.

최대값이 더해지는 횟수 = M/(K+1) * K + M%(K+1)

import java.util.Scanner;
import java.util.Arrays;

class q1 {
    public static void main(String args[]){
      Scanner kbd = new Scanner(System.in);
      int N, M, K;
      int count = 0, result = 0; 

      //N(배열의 크기), M(더해지는 횟수), K(연속 가능 횟수) 값 입력받기 
      System.out.println("N, M, K :");
      N = kbd.nextInt();
      M = kbd.nextInt();
      K = kbd.nextInt();

      //배열의 값 입력 받기 
      int arr[] = new int[N];
      for(int i = 0; i < N; i++)
        arr[i] = kbd.nextInt();
      
      Arrays.sort(arr); //오름차순 정렬 
      
      count = M/(K+1)*K + M%(K+1); //가장 큰 수 더해지는 횟수 계산 
      
      result += arr[N-1]*count; //가장 큰 수  
      result += arr[N-2]*(M-count); //2번째로 큰 수 
      
      System.out.println(result);

    }
}

 

추가 개념 정리)

*기본 타입 배열 정렬 - 라이브러리 사용하기 

사용 라이브러리 : java.util.Arrays의 sort() 메서드

예시)

1. 오름 차순 정렬

기본 타입 정렬 메서드

import java.util.Arrays;

class ArraysSort{
  public static void main(String args[]){
    int arr[] = {5,4,3,2,1};

    Arrays.sort(arr); //오름차순 정렬

    for(int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
  }
}

2. 내림 차순 정렬

기본 타입 배열을 Wrapper 클래스로 만들고, Comparator를 두 번째 인자에 넣어줘 내림차순 정렬을 할 수 있다. 이때 Comparator로 Collections 클래스의 reverseOrder()를 사용한다. 

import java.util.Arrays;
import java.util.Collections;

class ArraysSort{
  public static void main(String args[]){
    Integer arr[] = {1,2,3,4,5};

    Arrays.sort(arr, Collections.reverseOrder()); //내림차순 정렬

    for(int i = 0; i < arr.length; i++)
      System.out.print(arr[i] + " ");
  }
}

참고

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Collections.html

https://coding-factory.tistory.com/549