[1049번] 기타줄

문제 기출 : [https://www.acmicpc.net/problem/1049]

 

풀이 방법

[그리디 알고리즘]으로 접근 낱개의 가격과 6개세트의 가격을 별도로 array에 담는다. 그리고 각각의 가격에서 최소 값이면서 끊어진 라인의 수보다 크거나 같으면 된다.   최소값을 먼저 만족시키기위해 오름차순으로 sort 진행해서 가장 작은 0번째 값으로 먼저 체크하면 최대한 빠르게 찾을 수 있다.

 

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;

		try {
			StringTokenizer oneLine = new StringTokenizer(br.readLine(), " ");
			int crushLine = Integer.parseInt(oneLine.nextToken());
			int brands = Integer.parseInt(oneLine.nextToken());

			int[] manyAmounts = new int[brands];
			int[] oneAmounts = new int[brands];
			for (int i = 0; i < brands; i++) {
				oneLine = new StringTokenizer(br.readLine(), " ");
				manyAmounts[i] = Integer.parseInt(oneLine.nextToken());
				oneAmounts[i] = Integer.parseInt(oneLine.nextToken());
			}

			Arrays.sort(manyAmounts);
			Arrays.sort(oneAmounts);
			int oneMin = oneAmounts[0];
			int manyMin = manyAmounts[0];

			while (crushLine > 0) {
				if (crushLine < 6) {
					answer += Math.min(oneMin * crushLine, manyMin);
					crushLine -= 6;
				} else {
					if (oneMin * 6 >= manyMin) {
						crushLine -= 6;
						answer += manyMin;
					} else {
						crushLine -= 6;
						answer += (oneMin * 6);
					}
				}
			}

			System.out.println(answer);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}