[SWEA] 4050. 재관이의 대량 할인

문제

재관이의 옷 매장에서 대량 세일을 하고자 한다.

세일에는 조건이 한가지 있는데, 세 벌의 옷을 사면 그 중 가장 저렴한 한 벌에 해당하는 값은 내지 않아도 된다는 조건이다.

그리고 세 벌보다 많은 옷을 구매하는 경우에도 옷을 세 벌씩 나눠서 계산하면 같은 방식의 할인을 받을 수 있다.

예를 들면 10, 3, 2, 4, 6, 4, 9원짜리 옷을 사고자 할 때 (3, 2, 4), (10, 4, 9), (6)원짜리로 묶어서 계산을 하게 된다면,

첫 묶음에서 2원, 두 번째 묶음에서 4원 총 6원의 할인을 받게 되는 것이다.

다만 세 번째 묶음은 한 벌만 구매하므로 할인이 적용되지 않는다.

재관이네 매장에서 사고자 하는 옷이 있을 때 어떻게 묶어서 결제를 하면 가장 할인을 많이 받아서 구매를 할 수 있는지 계산하여라.

두 번째 테스트케이스를 예로 보면, {6,4,5,5,5,5}의 옷들이 있을 때 (6,4,5), (5,5,5)로 묶으면 가장 저렴한 조합이 된다.

 

풀이방법

그리디 알고리즘으로 해결한다.

 

가장 적은 액수를 내기 위해서는 가장 큰 금액을 할인받아야한다.

 

가장 큰 액수를 할인 받는 방법은 높은 가격 순으로 3개를 묶었을 때, 그 중에서 가장 작은 값을 할인받을 수 있게 된다.

 

예를 들어 {1, 2, 3, 4, 5, 6} 가격의 물건들을 구입했을 때,

 

가격이 높은 순으로 정렬하면 {6, 5, 4, 3, 2, 1}과 같다.

 

이 값들을 3개씩 묶으면 {6, 5, 4}, {3, 2, 1}이고, 따라서 4천원, 1천원, 총 5천원을 할인받을 수 있다.

 

입력받은 수들을 내림차순으로 정렬하고, i+2번째에 있는 값들을 제외한 합을 구한다.

 

단, 구입한 물건들을 3개씩 묶을 수 없는 경우는 3개씩 묶고 남은 물건은 가격이 제일 낮은 순으로 한다.

 

소스코드

package samsung;

import java.util.*;

public class s_4050 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			int n = sc.nextInt();
			ArrayList<Integer> a = new ArrayList<>();
			
			for(int i = 0; i < n; i++) {
				int tmp = sc.nextInt();
				a.add(tmp);
			}
			
			Collections.sort(a, Collections.reverseOrder());
			int sum = 0;
			for(int i = 0; i < n % 3; i++) {
				sum += a.get(n-1-i);
			}
			
			int i = 0;
		
			while(i + 2 < n) {
				sum += a.get(i);
				sum += a.get(i+1);
				i += 3;
			}
			
			System.out.println("#" + t + " " + sum);
		}
	}
}