원래는 백트래킹 문제들만 풀자 했었는데 어쩌다가 문제추천에 나와가지고 봤는데 일단 제목부터 너무 귀여웠어가지고 한번 풀어보자 했던 문제이다. 코코라는 원숭이 추정인 생물체가 있는데 코코는 주어진 시간 h 안에 piles 라는 벡터안에있는 숫자의 바나나를 전부 먹어야 한다고 한다. 이때, 코코가 시간안에 파일안에 있는 모든 바나나를 먹을수있는 최소의 k를 구해야하는게 이 문제의 핵심.
문제를 다 읽자마자 솔직히 조금 헷갈렸다 문제의 유형이 뭐일지. 그러나 좀 읽다보니 이건 이진탐색 문제라는게 확실했다. piles 안에있는 가장 큰 숫자의 바나나만큼만 먹으면 전부다 먹을수있지만 그건 주어진 시간 h 보다도 너무 앞서고 우리는 최소한의 시간을 구해야한다.
결국 내가 선택한 방법은 숫자 1부터 시작해서 piles안에 최대숫자의 평균인 mid 를구해서 비교를 한다음에 check 라는 함수로 계산을 하고 가장 최솟값을 구하는 방식을 선택했다. 만약 h보다 시간이 낮거나 같으면 최소값을 위해 범위를 좁혔고 h보다 높으면 시작점을 더 높게 잡았다. check 함수에서 계산하는 방법은 다른 사람의 풀이를 통해 참고하였다.
이 문제는 카카오에서 나왔던 징검다리 건너기와 굉장히 유사하단걸 느꼈다. 만약 이 문제를 풀고 징검다리 건너기를 풀었다면 훨씬 수월했을것만 같은 느낌이든다.
배운점:
1. 이진탐색의 활용
2. 숫자 계산법
성장하는 사람