[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으로 위 상황을 방지할 수 있다.

 

---

🌱 코드 및 풀이

 

---

🌱 느낀 점

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