15459번 Haybale Feast [BOJ]
2021. 4. 12. 11:52ㆍ백준
15459번: Haybale Feast
The first line contains the integers $N$ and $M$, the number of haybales and the minimum total flavor the meal must have, respectively. The next $N$ lines describe the $N$ haybales with two integers per line, first the flavor $F$ and then the spiciness $S$
www.acmicpc.net
해설보지않고 내힘으로만 푼 플레5문제라 더 의미있고 뜻깊은 문제였던것같다
솔직히 영어문제여서 그런가 개날먹문제다
알고리즘 태그 : 이분탐색
문제 설명
최소 맛 필요조건(M)을 만족하는 최소의 맵기를 찾으면된다
싱글코스 -> 이말이 좀 애매하긴한데 감당할 수 있는 맵기의 건초를 차지하고 그 양옆의 건초을 확인하며 차지하면된다
간단하게 말해서 뭉쳐있는 건초라고 보면될듯하다
만약 위처럼 건초가 있고 가능한 맵기가 9라면
3,4번건초를 먹었을때 최대 맛(13)을 가져갈 수 있다
근데 여기서 모든 맵기에대해서 탐색을하면 시간초과에 걸리므로
이분탐색을 이용해 맵기를 키값으로 놓고 탐색을 진행하면된다
