[백준][이분탐색] 15732번 도토리 숨기기

문제 

다람쥐가 도토리를 뺏기지 않기 위해 숨기는 문제입니다.(귀여워) N개의 상자가 있을 때 임의의 규칙에 의해서 차례대로 도토리를 상자에 채워나가야하는데 마지막 도토리가 들어가는 상자의 번호를 출력합니다.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/15732)

풀이

저는 이 문제가 이분탐색로 접근해야한다는 것을 알고 푼 문제인데 아니라면 처음 접근하기가 어려웠을 것 같습니다. 문제의 규칙은 어렵지 않아서 하나씩 다 해보면 되지않을까하는 생각도 들지만 개수의 범위가 매우 크기때문에 도토리 하나씩 넣기에는 힘들거라 생각이 들었습니다. (범위가 크기 때문에 long long 타입을 써야합니다.) 이분탐색을 어떻게 적용해볼 수 있을까? 고민을 해보고 줄여나가는 범위가 상자의 번호라는 것을 생각하니 쉽게 접근할 수 있었습니다. 처음의 범위를 [1, N]으로 하고 이분탐색을 시작합니다. while문을 통해 mid값이 정해지면 해당 번호까지 도토리를 몇 개 넣을 수 있는지 계산을 합니다. 만약 mid보다 임의의 규칙이 먼저 끝나면 해당하는 규칙으로 넣을 수 있는 모든 도토리의 수를 더하고, mid보다 규칙의 시작보다 늦다면 넣을 수 있는 도토리가 없습니다. 규칙의 시작과 규칙의 끝 사이에 mid가 있다면 규칙의 시작에서 mid까지 가능한 수를 더해줍니다. 실제 값으로 예를 들어보면 규칙이 100 150 10 일 때 mid 값에 따라 (규칙의 마지막값-규칙의 시작값)/규칙의 간격+1 또는 (mid-규칙의 시작값)/규칙의 간격+1 을 해주면됩니다. 만약 해당하는 번호까지 넣을 수 있는 도토리 수가 가지고 있는 도토리 수보다 많다면 상자 번호를 줄이기 위해 high=mid 해줘야할 것이고, 도토리 수보다 작다면 더 많은 도토리를 넣기 위해 low=mid 해줘야할 것입니다. 이렇게 하면 상당히 큰 값이 들어와도 이분탐색을 통해서 빠르게 계산됩니다.

이분탐색문제들을 풀어보다보면 어떤 것을 타겟으로 잡을지만 정하면 쉽게 생각해낼 수 있다는 것을 알 수 있습니다!

+ 평소엔 제출할 때 한 부분 고치고 제출하고 틀리면 또 바로 제출해보고 하다보니 상당히 정답률이 낮아져서.. 앞으로는 신중하게 코드를 짜고 제출하려고 합니다. 한번에 받은 맞았습니다!! *^^*

코드

https://github.com/kswim/Algorithm/blob/master/BinarySearch/15732.cpp