[백준] 11508번 - 2+1 세일 (Java)

https://www.acmicpc.net/problem/11508

11508번: 2+1 세일

 

 

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팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

 

 

입력

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

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

 

 

출력

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

 

 

예제 입력 1

4
3
2
3
2

예제 출력 1

8

 

예제 입력 2

6
6
4
5
5
5
5

예제 출력 2

21

 

힌트

예제 1 : 재현이가 (3, 2, 2), (3)으로 총 2번에 걸쳐서 유제품을 사면 됩니다.

예제 2 : 재현이가 (6, 4, 5), (5, 5, 5)로 총 2번에 걸쳐서 유제품을 사면 됩니다.

 

 

나의 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[] C = new int[N];
		
		for(int i=0; i<N; i++) {
			C[i] = scan.nextInt();
		}
		
		Arrays.sort(C);
        
		int num = N/3;
		int cost = 0;
		
		for(int i=1; i<=N; i++) {
			if(i <= num*3 && i%3 == 0) {
				continue;
			} else {
				cost += C[N-i];
			} 
		}
		
		System.out.println(cost);
			
	}

}

 

※ 체크

1. 유제품을 가격 낮은 것부터 오름차순으로 정렬한다.

2. 유제품의 갯수(N)를 3으로 나눈 몫을 변수 num에 저장한다.

3. num*3은 유제품의 갯수(N) 중에서 3의 최대 배수를 나타낸다.(예를 들어 유제품이 7개일 경우 6을 나타냄)

4. 유제품의 갯수(N) 중에 3의 최대 배수까지는 3의 배수 번째(각 3개 중에 가격이 가장 큰 것)를 제외 하고는 다 더한다.