2022.01.19 28일차

백준 11508번 (2+1 세일)

문제

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

나의 풀이

1. 3개가 기준, 나머지가 1이거나 2일때 예외 기준
2. N을 감소시키면서 접근
3. 감소하는 값이 더 적어서 합은 다 더하고 시작
4. 3으로 나누었을 때 나머지가 0이면 N은 3씩 감소, 카운트에 해당하는 인덱스는 값은 합에서 감소, 카운트 인덱스는 3씩 증가

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int[] nArr = new int[N];

        int sum = 0;

        for (int i = 0; i < N; i++) {
            nArr[i] = scanner.nextInt();
            sum += nArr[i];
        }

        Arrays.sort(nArr);

        int count = 0;
        while(N > 0) {
            if (N % 3 == 1) {
                N -= 1;
                count += 1;
            }

            if (N % 3 == 2) {
                N -= 2;
                count += 2;
            }

            if (N % 3 == 0) {
                sum -= nArr[count];
                N -= 3;
                count += 3;
            }
        }

        System.out.println(sum);
    }
}

생각하기