/ BOJ

BOJ_1049_기타줄_JAVA

문제 : 기타줄

링크 : BOJ_1049_기타줄

접근 방식

거스름돈 남기기와 비슷한 문제이다.

가장 최우선으로 낱개 줄의 가격 * 6이 6개 세트의 최소 가격보다 더 싼 경우가 있다면, 해당하는 낱개 줄을 N개만큼 구매하면 된다.

두번째로, 6개 세트의 최소 가격이 낱개 *6보다 더 싼 경우라면, 일단 6개 세트로 6개이하로 남을 때 까지 구매한 후, 마지막에 6개 세트를 사는 것과 낱개를 사는 가격을 비교해서 더 싼 경우를 선택하면 된다.

그리디 알고리즘의 기본적인 구성을 사용한 간단한 문제이다.

소스 코드


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

public class BOJ_1049_기타줄 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine()," ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int arr[][] = new int[M][2];
		int min = Integer.MAX_VALUE;
		int min2 = Integer.MAX_VALUE;
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<2;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
			if(arr[i][0] < min) {
				min = arr[i][0];
			}
			if(arr[i][1] < min2) {
				min2 = arr[i][1];
			}
		}

		if(min2*6 < min) {
			System.out.println(min2*N);
			return;
		}
		int answer = 0;
		while(true) {


			if(N - 6 < 0) {
				if(min2*N < min) {
					answer = answer + min2*N;
				}else {
					answer = answer + min;
				}
				break;
			}
			N = N - 6;
			answer = answer + min;
		}
		System.out.println(answer);


	}

}