[코드트리] 3개씩 묶기 - 자바(Java)

문제

https://www.codetree.ai/problems/bundle-by-3?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

n개의 정수가 주어집니다. 이 정수들은 1개 ~ 3개 단위로 묶어서 제거해 가며 모든 정수를 제거하려 합니다. 제거할 때마다 제거되는 수들의 합을 더해주는데, 이때 3개로 묶어서 제거하는 경우에는 그중 가장 작은 값 하나는 더하지 않아도 된다고 합니다.

모든 정수를 제거했을 때 제거되는 수들의 합이 최소가 되게 구하는 프로그램을 작성하세요.

 

입력 예시

6
6 4 5 5 5 5

 

출력 예시

21

 

 

코드

첫 번째 줄에 정수의 개수 n이 주어집니다.

두 번째 줄에 n개의 정수가 공백을 두고 주어집니다.

• 1 ≤ n ≤ 100,000
• 1 ≤ 주어진 정수의 값 ≤ 1000

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums); // 오름차순 정렬

        int count = 0;
        int result = 0;
        // 큰 수부터 순회
        for (int i = n - 1; i >= 0; i--) {
            count++;
            // 큰 수부터 3개씩 묶어서 처리하여 작은 수 무시
            if (count % 3 == 0) {
                continue;
            }
            // 제거되는 수들의 합
            result += nums[i];
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
}