SWEA 4050. 재관이의 대량 할인 :: 돼지개발자

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIseXoKEUcDFAWN&categoryId=AWIseXoKEUcDFAWN&categoryType=CODE

"그리디"

당연히 좀 더 큰 금액을 할인 받는것이 전체 금액이 최소가 된다. 따라서 주어진 가격을 내림차순 정렬하여 세 개 상품씩 그룹을 지어 가장 작은 가격을 더해 총 할인액을 구하는 것이 할인이 최대인것.

그리디.

내림차순 정렬하고 선택한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
class Solution {
    
    static int T,N;
    static Integer[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        T = Integer.parseInt(br.readLine());
        
        int t = 1;
        while(T-- > 0 ) {
            N = Integer.parseInt(br.readLine());
            
            arr = new Integer[N];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int total = 0;
            
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                total += arr[i];
            }
            
            Arrays.sort(arr, Collections.reverseOrder());
            
            int sale = 0;
            for (int i = 2; i < N; i+=3) {
                sale += arr[i];
            }
            System.out.printf("#%d %d\n",t++,total-sale);
        }
    }
}