#23559 : 밥

풀이방법

사용된 것:

그리디 알고리즘

정렬

Comparator 재정의

 

2022.02.24

각 날마다,

5000원짜리와 1000원짜리 중 무조건 더 맛있는 것을 고른다.

두 메뉴의 맛수치가 같다면 1000원짜리를 고른다.

 

그 후, 사용할 돈이 예산을 초과하는지 체크한다. 초과하지 않는다면 지금의 맛수치 합을 출력하고 프로그램을 종료한다.

 

예산을 초과한다면 다음과 같이 돈 아끼기를 수행한다.

 

일단, 각 날마다 '맛손실'을 구한다.

맛손실이란, 5000원짜리를 고르지 않고 1000원짜리를 골랐을 때 손해보는 맛수치의 크기이다.

즉, (5000원짜리의 맛수치 - 1000짜리의 맛수치) 이다.

1000원짜리가 더 맛있는 날에는 맛손실이 음수이다.

 

맛손실을 기준으로 날들을 오름차순 정렬한다.

그 후, 정렬된 배열의 앞부터 즉 맛손실이 적은 것부터 차례차례 방문한다.

만약 해당 날의 맛손실이 음수라면 이미 최적의 선택을 한 것이므로 이 날의 선택은 바꾸지 않고 넘어간다.

만약 해당 날의 맛손실이 양수라면 선택을 1000원짜리로 바꾸어준다.

즉 사용할 돈 합계에서 4000원을 빼주고, 맛수치 총합에서도 맛손실만큼을 빼준다.

 

선택을 1000원짜리로 바꿀 때마다, 사용할 돈 합계가 예산 이하가 되었는지를 체크해준다.

예산 이하가 된 순간 즉시 돈 아끼기를 종료하고 맛수치 총합을 출력하고 프로그램을 종료한다.

 

돈 아끼기를 할 때 맛손실이 적은 것부터 선택을 바꾸면 되므로 그리디 알고리즘 문제이다.

 

코드

Java(2022.02.24)

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

public class Main {

	static int n, budget;
	static Day[] days;
	static int sum_m, sum_t;	//돈 합계, 맛 합계
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//Day 객체들을 맛손실을 기준으로 오름차순 정렬하는 Comparator
		Comparator<Day> cp = new Comparator<Day>() {

			@Override
			public int compare(Day o1, Day o2) {
				// TODO Auto-generated method stub
				int sub1 = o1.sub;
				int sub2 = o2.sub;
				
				//수의 크기를 기준으로 오름차순 정렬
				if(sub1>sub2)return 1;
				if(sub1==sub2)return 0;
				else return -1;
			}
			
		};
		
		//날 수와 예산 읽어오기
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		budget = Integer.parseInt(st.nextToken());
		days = new Day[n];
		//각 날의 맛수치 읽어오기
		sum_m = 0;
		sum_t = 0;
		for(int i = 0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			days[i] = new Day(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			if(days[i].choice) {
				sum_m += 5000;
				sum_t += days[i].five;
			}
			else {
				sum_m += 1000;
				sum_t += days[i].one;
			}
		}
		
		if(sum_m<=budget) {
			System.out.print(sum_t);
			System.exit(0);
		}
		
		//Day 객체들을 맛손실 기준으로 오름차순 정렬
		Arrays.sort(days, cp);
		for(int i = 0; i<n; i++) {
			//1000원짜리가 더 맛있는 날은 그냥 패스
			if(!days[i].choice) continue;
			
			//5000원짜리가 더 맛있는 날 중, 1000원짜리로 바꿀 때의 맛손실이 작은 것부터 선택을 바꾸기.
			sum_m -= 4000;	//바꿔서 절약한 돈을 합계에 반영
			sum_t -= days[i].sub;	//바꿔서 생긴 맛손실을 합계에 반영
			//반영 후 지출이 예산 이내라면 반복문 종료
			if(sum_m<= budget) break;
		}
		
		System.out.print(sum_t);

	}

}

//각 날의 데이터를 저장하는 객체
class Day{
	int five;	//5000원짜리 메뉴의 맛수치
	int one;	//1000원짜리 메뉴의 맛수치
	int sub;	//5000원 -> 1000원 으로 바꿀 경우의 맛손실(음수일 수도 있음)
	boolean choice;	//true면 5000원짜리 메뉴를, false면 1000원짜리 메뉴를 선택한 것
	
	public Day(int five, int one) {
		this.five = five;
		this.one = one;
		sub = five - one;
		if(five>one) choice = true;	//5000원짜리가 더 맛있는 날은 초기값으로 5000원짜리 선택
		else choice = false;	//1000원짜리가 더 맛있는 날은 초기값으로 1000원짜리 선택
	}
	
}