[BOJ] 백준 23559 밥 (JAVA)

그리디는 어려워..

📑 문제

 

백준 23559 밥

---

🌱 아이디어

DP 문제처럼 생긴 그리디 문제.... 결국 알고리즘 분류 보고 풀었다..

 

이 문제에서 생각해야 하는 부분은 2가지 정도 있다.

 

1. A메뉴, B메뉴를 어떤 기준으로 선택할 것 인지?

2. 5000원 메뉴인 A메뉴를 돈이 부족해 선택을 하지 못할 때.

 

[1번 경우]

다른 그리디 문제는 정렬 시 데이터에서 하나의 기준을 잡아 정렬하는 경우가 많다.

위 문제는 정렬의 기준을 (A메뉴 - B메뉴)의 차이를 기준으로 내림차순으로 정렬한다

 

ex) 1000 999 보다 10 1 이 우선순위가 되어야 한다.

 

[2번 경우]

1번 경우에서 5천 원 메뉴를 선택하다 보면 나머지 날은 밥을 먹지 못하는 경우가 생길 수도 있다.

위 경우를 방지하기 위해 M - 5000 >= 남은 요소 * 1000으로 위 상황을 방지할 수 있다.

 

---

🌱 코드 및 풀이

	public class Main {
	public static class node implements Comparable<node> {
	int a, b;
	public node(int a, int b) {
	this.a = a;
	this.b = b;
	}
	@Override
	public int compareTo(node o) {
	// A,B 메뉴의 차이가 큰 순서로 정렬.
	return Math.abs(o.a - o.b) - Math.abs(a - b);
	}
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	PriorityQueue<node> pq = new PriorityQueue<node>();
	StringTokenizer st;
	st = new StringTokenizer(br.readLine());
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	int answer = 0;
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	pq.offer(new node(a, b));
	}
	while (!pq.isEmpty()) {
	node now = pq.poll();
	// 현재 5천원 메뉴를 선택 해도 -> 마지막 날까지 밥을 사 먹을 수 있는지 판단.
	if (M - 5000 >= pq.size() * 1000 && now.a > now.b) {
	M -= 5000;
	answer += now.a;
	} else {
	// B 메뉴가 더 크다면 먹기.
	M -= 1000;
	answer += now.b;
	}
	}
	System.out.println(answer);
	}
	}

view raw 밥.java hosted with ❤ by GitHub

 

---

🌱 느낀 점

DP, Greedy는 볼 때마다 헷갈린다 여러 문제를 풀어보면서 느낌을 익히는 게 중요할 것 같다.