[백준] 1049번: 기타줄(그리디, 구현)

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

1049번: 기타줄

틀린 코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();		// 끊어진 기타줄의 갯수
		int M = scan.nextInt();		// 기타줄 브랜드
		int payMoney = 0;			// 지불해야 하는 돈의 최솟값
		int minPackageMoney = 1000;	// 각 브랜드별 패키지 가격 최솟값
		int minEachOfMoney = 1000;	// 각 브랜드별 낱개의 가격 최솟값
		int[][] arr = new int[M][2];
		int[][] arr2 = arr.clone();
		for(int i=0; i<arr.length; i++) {
			arr[i][0] = scan.nextInt();	// 각 브랜드별 패키지 가격
			arr[i][1] = scan.nextInt();	// 각 브랜드별 낱개의 가격
		}
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i][0] < minPackageMoney) 
				minPackageMoney = arr[i][0];
			if(arr[i][1] < minEachOfMoney)
				minEachOfMoney = arr[i][1];
		}
		
		// 패키지로 살 때보다 낱개로 사는게 이득인 경우
		if(minPackageMoney >= minEachOfMoney * 6) {
			payMoney +=  N * minEachOfMoney;
		}
		// 낱개로 살 때보다 패키지로 사는게 이득인 경우
		else {
			payMoney += (N/6) * minPackageMoney;	// 패키지 가격으로 구매
			N -= (N/6) * 6;	// 낱개로 구매하기 위해 패키지로 구매한 갯수 빼기
			payMoney += N * minEachOfMoney;			// 낱내의 가격으로 구매
		}
		
		System.out.println(payMoney);
		
//		// 각 브랜드별 패키지 가격을 기준으로 오름차순 정렬
//		Arrays.sort(arr, new Comparator<int[]>() {
//			@Override
//			public int compare(int[] arr1, int[] arr2) {
//				return Integer.compare(arr1[0], arr2[0]);
//			}
//		});
//		
//		// 각 브랜드별 낱개의 가격을 기준으로 오름차순 정렬
//		for(int i=0; i<arr2.length; i++) 
//			Arrays.sort(arr[i]);
//
//		// 낱개로 살 때보다 6개 패키지로 살 때가 저렴할 경우
//		if(arr[0][0] <= arr2[0][0] * 6) {
//			money += (N/6) * arr[0][0];	// 패키지를 구매해야 하는 가격
//			N -= N * (N/6);				// 패키지를 구매하고 남은 갯수
//			money += N * arr2[0][0];	// 낱개를 구매해야 하는 가격
//		}
//		// 6개의 패키지 가격보다 낱개로 살 때가 저렴할 경우
//		else {
//			money += N * arr2[0][0];
//		}
//		System.out.println(money);
		scan.close();
	}

}

풀이

무슨 이상하게는 다 풀어본 것 같다..

​

간단하게 브랜드별 패키지, 낱개로 구매하는 가격이 주어졌을 때,,

패키지로 구매하는게 저렴한지, 낱개로 구매하는게 저렴한지 두 개 섞어서 구매하는게 더 저렴한지 판단하면 되는 간단한 문제인데 ..

​

처음엔(주석 부분) 패키지별로 정렬하고, 낱개별로 정렬하고

패키지로 구매하는 게 저렴한지, 낱개로 구매하는게 저렴한지(6개 가격 비교) 비교해서 저렴한걸로 출력했는데

틀렸습니다 ...

​

두번째론 각 패키지, 낱개 가격의 최솟값을 구해서 다시 패키지와 낱개중 뭐로 구매하는게 저렴할지 비교해서 출력했는데 ... 또 틀렸습니다 ..

​

왜그런지 모르다가 다른 블로그를 참고하니 반례가 있었다...

​

패키지 + 낱개를 섞어서 구매하는 경우인데,

만약 필요한 기타줄의 개수가 23개이고,

가장 저렴한 패키지(6개)의 가격: 50

가장 저렴한 낱개(1개당)의 가격: 20

이라고 가정해보자..

​

위 경우 낱개를 사는거보다 패키지를 사는게 더 저렴한데,

세트 3개를 구하면 5개의 기타줄이 남고,

세트 1개를 더 구매할경우 => 50원

낱개 5개를 구매할경우 => 100원,

따라서 세트를 구매하는게 훨씬 더 저렴하다!

​

나는 이때까지 세트가 더 저렴할경우 => 세트를 구매하고 나머지는 항상 낱개로 구매했었다...

​

따라서 3가지의 케이스를 전부 비교해서 최솟값을 찾으면 된다.

1. 전부 패키지로 구매했을 경우

2. 전부 낱개로 구매했을 경우

3. 패키지 + 낱개 섞어서 구매했을 경우

​

​

최종 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();		// 끊어진 기타줄의 갯수
		int M = scan.nextInt();		// 기타줄 브랜드
		int payMoney = 0;			// 지불해야 하는 돈의 최솟값
		int[] pack = new int[M];	// 각 브랜드별 패키지 가격
		int[] unit = new int[M];	// 각 브랜드별 낱개의 가격
		for(int i=0; i<M; i++) {
			pack[i] = scan.nextInt();
			unit[i] = scan.nextInt();
		}
		
		// 패키지, 낱개 가격 정렬
		Arrays.sort(pack);
		Arrays.sort(unit);
		
		// 낱개로 살 때보다 패키지로 사는게 이득인 경우
//		if(pack[0] <= unit[0] * 6) {
//			payMoney += (N/6) * pack[0];
//			payMoney += (N%6) * unit[0];
//		}
//		else {
//			payMoney += N * pack[0];
//		}
		
		// 1) 전부다 패키지 세트로 구매하는 경우 - ((N/6) + 1) * pack[0]
		// 2) 전부다 낱개로 구매하는 경우		 - (N * unit[0])
		// 3) 패키지 + 낱개 섞어서 구매하는 경우 - ((N/6) * pack[0]) + ((N%6) * unit[0])
		payMoney = Math.min(((N/6) + 1) * pack[0], Math.min(N * unit[0], ((N/6) * pack[0]) + ((N%6) * unit[0])));
		
		System.out.println(payMoney);
		scan.close();
	}

}