[백준 20117번 / java] 호반우 상인의 이상한 품질 계산법

문제

20117번: 호반우 상인의 이상한 품질 계산법 (acmicpc.net)

묶음 -> 모든 호반우의 품질이 '중앙값'이 됨

중앙값 = 
짝수 : (묶음 개수/2) +1번째 숫자
홀수 : (묶음 개수+1) /2번째 숫자

최대 이익을 출력

풀이

묶음이 짝수, 홀수인 경우 나눠서 값을 계산하고, 가장 큰 값을 출력해야 한다.

 

최대한 큰 값이 선택되게 해야 한다.
-> 묶인 개수가 짝수면 '중앙+1' 에 가장 큰 값을 위치시켜야 한다.
-> 묶인 개수가 홀수면 '중앙'에 가장 큰 값을 위치시켜야 한다.

최대한 큰 값을 최대한 많이 선택하게 해야 한다.
-> 묶음의 개수가 많을 수록 최대값이 더 많이 선택된다? -> 맞음
-> 묶음 내의 호반우 개수가 많을 수록 최대값이 더 많이 선택된다? -> 아님

 

처음에는 중간값의 의미를 그냥 중간에 둔 값으로 이해하고 예제1이 잘못된 게 아닌가 했다.

중간값이란 정렬 시 중간에 있는 값을 의미하는 것이다.

이걸 이해하고 나니 아이디어가 바로 떠올랐다.

 

제일 큰 수를 가장 많이 카운트하도록 묶으려면, 짝수일 때는 무조건 두 개씩 짝지어야 한다.

호반우가 묶음 속에서 오름차순으로 정렬되고, 묶음 속의 모든 값이 중간값으로 치환되니까

묶음 속의 모든 값을 그 중 가장 큰 값으로 치환하려면 무조건 두 개씩 짝지어야 한다.

 

홀수로 묶으면 손해일 수밖에 없다. (3 10 6) 이렇게 묶으면 3개 다 가장 큰 값이 아닌 6으로 치환된다.

따라서 최대한 (가장 작은 값, 가장 큰 값)으로 묶는 작업을 진행하는 것이 방법이다.

 

1. 호반우의 품질을 정렬
2. (가장 작은 값, 가장 큰 값)으로 최대한 묶는다
3. 최대 이익을 계산한다

N이 짝수면 정렬 후 N/2로 나누어 뒷부분에 대해 (값*2)를 전체 이익에 누적한다.
N=6
012345 ->345*2

N이 홀수면 정렬 후 N/2로 나누어 뒷부분에 대해 (값*2)를 전체 이익에 누적하고, 가운데 있는 값을 더한다.
N=7
0123456 ->456*2 + 3

코드

import java.io.*;
import java.util.*;

public class boj_20117 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int sum = 0;

        if(N%2 == 0){
            for(int i=N/2; i<N; i++){
                sum += arr[i] * 2;
            }
        }else{
            for(int i=N/2+1; i<N; i++){
                sum += arr[i] * 2;
            }
            sum += arr[N/2];
        }

        bw.write(sum + " ");
        bw.close();
    }
}