[BaekJoon] 1049 기타줄

1.  문제 링크

2.  문제

요약

• 총 n개의 줄이 끊어져서 줄을 교체하려고 하는데 m개의 브랜드의 줄이 존재합니다.
• 줄 6개가 들어가있는 패키지로 구매할 수도, 낱개로 구매할 수도 있는데 n개의 줄을 교체하려고 할 때 최소 금액을 출력합니다.
• 금액은 0보다 크거나 같은 자연수이고 패키지의 가격이 낱개의 가격보다 낮을 수도 있습니다.
• 입력: 첫 줄은 끊어진 줄의 개수 n, 브랜드의 개수 m이 주어지고 그 다음부터 m개의 줄에는 패키지 가격, 낱개 가격이 주어집니다.
• 출력: 최소 금액을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	public int getMinPrice(int n, ArrayList<Integer> pack, ArrayList<Integer> unit) {
		Collections.sort(pack);
		Collections.sort(unit);
		int minPrice = 0;
		if(pack.get(0) == 0 || unit.get(0) == 0) {
			return 0;
		}
        if(n == 1) {
			if(pack.get(0) > unit.get(0)) {
				minPrice = unit.get(0);
			} else {
				minPrice = pack.get(0);
			}
			return minPrice;
		}
		if(pack.get(0) > unit.get(0)) {
			int defer = pack.get(0) / unit.get(0);
			if(defer >= 6) {
				minPrice = n * unit.get(0);
			} else {
				int quote = n / 6;
				int remainder = n % 6;
				if(remainder > defer) {
					minPrice = (quote + 1) * pack.get(0);
				} else {
					minPrice = (quote * pack.get(0)) + (remainder * unit.get(0));
				}
			}
		} else {
			if(n % 6 == 0) {
				minPrice = pack.get(0) * (n / 6);
			} else {
				minPrice = pack.get(0) * (n / 6 + 1);
			}
		}
		return minPrice;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		ArrayList<Integer> pack = new ArrayList<Integer>();
		ArrayList<Integer> unit = new ArrayList<Integer>();
		for(int i = 0; i < m; i++) {
			String price = br.readLine();
			st = new StringTokenizer(price);
			pack.add(Integer.parseInt(st.nextToken()));
			unit.add(Integer.parseInt(st.nextToken()));
		}
		Main main = new Main();
		System.out.println(main.getMinPrice(n, pack, unit));
	}
}

4.  접근

• 만약 패키지나 낱개 가격에 0이 존재한다면 몇 개의 줄을 교체하던간에 0원이 필요하므로 0을 출력합니다.
• 만약 끊어진 줄의 개수가 1이라면 낱개 가격과 패키지 가격 중 가장 낮은 금액인 것을 이용하면 되므로 가장 낮은 금액을 출력합니다.
• 최소 금액을 이용해야하기 때문에 패키지를 이용할 때에도 패키지 금액 중 가장 낮은 금액을, 낱개를 이용할 때에도 낱개 금액 중 가장 낮은 금액을 이용해야 합니다. 그래서 패키지 금액이 들어간 리스트와 낱개 금액이 들어간 리스트를 오름차순으로 정렬하여 가장 낮은 금액만 사용합니다.
• 만약 패키지 금액이 낱개 금액보다 낮다면 6개의 줄을 1개의 줄보다 낮은 금액으로 교체할 수 있으므로 패키지 금액만 이용하여 교체하면 최소 금액이 됩니다.
• 만약 패키지 금액이 낱개 금액보다 높다면, 낱개로 6개를 교체하는 금액과 패키지 금액을 비교하여 낱개로 6개를 교체하는 금액이 더 낮은 경우와 더 높은 경우로 나눌 수 있습니다.
• 더 낮은 경우에는 패키지를 이용하는 것이 더 많은 돈을 이용하게 되므로 모든 줄을 낱개로 교체하면 최소 금액이 됩니다.
• 더 높은 경우에는 패키지를 이용하여 6줄씩 교체한 후에 남은 줄을 낱개로 교체하는 금액보다 패키지 금액이 높다면 낱개로 교체하고 낮다면 패키지를 이용하여 교체한다면 최소 금액이 됩니다.