[백준] 2+1 세일

문제 출처: https://www.acmicpc.net/problem/11508

11508번: 2+1 세일

 

1. 입력

: 첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

: 두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

 

 

2. 출력

: 재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 231-1보다 작거나 같다.

 

3. 풀이

: 되도록이면 비싼 유제품들을 무료로 살 수 있도록 해야한다.

: 먼저 정렬한 후 비싼 순서로 3개씩 묶어가며 그 값을 빼줄 수 있도록 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N= Integer.parseInt(br.readLine());

		int[] arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr);
		
		int res = 0;
		int cnt = 0;
		for(int i = N-1; i >= 0; i--) {
			cnt++;
			if(cnt % 3 != 0) {
				res += arr[i];
			}
		}
		System.out.println(res);
	}
}