[BOJ] 20117 - 호반우 상인의 이상한 품질 계산법

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/20117

20117번: 호반우 상인의 이상한 품질 계산법

난이도: 실버 1

사용언어: JAVA

 

호반우는 품질에 따라 등급이 숫자로 매겨집니다. 호반우 상인들은 N개의 호반우를 개별적으로, 또는 묶음으로 판매할 수 있습니다. 그리고 등급과 같은 가격으로 호반우를 판매합니다.

 

호반우 상인들은 이윤을 최대화하기 위해 묶음으로 호반우를 판매할 경우, 호반우의 품질을 호반우 묶음의 중간값으로 통일하여 판매합니다. 짝수 개의 묶음일 경우 (묶음 개수/2+1) 번째를, 홀수 개의 묶음일 경우 ((묶음 개수+1)/2) 번째를 중간값으로 정의합니다.

 

이때, 호반우 상인들을 위해 호반우들의 총 등급을 최대화시키는 프로그램을 작성하는 것이 목적입니다.

 

풀이

이 문제는 단순한 하나의 아이디어만 캐치할 수 있다면, 쉽게 풀 수 있는 문제입니다. 이 아이디어란 바로, 두 개씩 묶음을 만들면 두 개의 호반우 모두 둘 중 더 큰 호반우의 품질로 통일된다는 것입니다. 

 

그래서 호반우의 품질이 들어있는 배열을 오름차순 정렬을 하여, 가장 큰 값으로부터 N/2까지의 값을 두 배 시켜주기만 하면 됩니다. N이 홀수인 경우에는 나머지 연산은 짝수와 똑같이 하고, 중간값만 총합에 더해주기만 하면 됩니다. (중간에 남는 하나의 값은 묶음이 아니라 개별로 판매되기 때문에)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N;
        N = Integer.parseInt(br.readLine());
        int i;
        int[] arr = new int[N];
        
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        for (i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int sum = 0;
       Arrays.sort(arr); // 배열을 소팅
        if (N % 2 == 0) { // 짝수일 경우에는
            for (i = N - 1; i >= N / 2; i--) {
                sum += arr[i] * 2; // 가장 마지막 수 부터 N/2까지 두 배 하여 합해주기만 하면 되고,
            }
        } else { // 홀수일 경우에는
            for (i = N - 1; i > N / 2; i--) {
                sum += arr[i] * 2; // 가장 마지막 수 부터 N/2 + 1까지 두 배 하여 합쳐주고,
            }
            sum += arr[i]; // 중간 값은 한 번 더해주기만 하면 됩니다.
        }
        System.out.println(sum);
    }
 
}