[백준 / BOJ] 15732 도토리 숨기기

문제

출처 : https://www.acmicpc.net/problem/15732

15732번: 도토리 숨기기

수형이는 N개의 상자에 도토리를 숨기려한다. 이때, 도토리를 숨긴위치를 기억하기 쉽게하기위해 규칙있게 숨긴다.

 

예를들어, A상자부터 B상자까지 C간격으로 도토리를 숨긴다면, A 상자에 하나를 숨기고, A+C상자에 하나를 숨기고, A+2C상자에 하나를 숨기고..B상자에 마지막하나를 숨긴다.

 

상자의 수 N, 도토리의 수 D, 숨기는 규칙의수 K가 주어질때, 마지막 도토리를 넣는 상자의 번호를 출력하는 문제다.

 

풀이

결정문제로 풀리는 문제였다.

 

결정문제란 어떠한 문제의 답을 구해야할때, "답을 임의의 지점a로 정했을때 반환값이 답을 만족하는가?" 에 대한 질문을 하고 답을 구하는 기법이다.

-> 만족한다 :  구간을 늘리거나 줄여가며(문제에따라) 다음 지점 a가 답을 만족하는지 구한다.

-> 불 만족한다 : 구간을 늘리거나 줄여가며(문제에따라) 다음 지점 a가 답을 만족하는지 구한다.

이를 이분탐색을 통해 수행한다.

 

임의의 상자 번호를 boxIdx라고하자.

상자는 1번부터 N번까지 있으므로, boxidx또한 1번부터 N번까지 갈수있을것이다.

 

이제 이 문제를 결정문제로 바꿔보자.

 

"상자의 번호를 i(1 <= i <= N)로 정했을때 구간(1,i)의 상자에 도토리를 전부 집어넣을수있는가?" 에 대한 답을 구하면 된다.

 

이 문제의 경우, 도토리를 구간(1,i)의 상자에 모두 집어넣을수있다면, 더 작은 상자에서도 도토리를 전부 집어넣을수있는지 확인하기위해 i를 mid-1로 바꾼다.

아니라면 1을 mid+1로 바꾸며 계산한다.

 

시간복잡도는 

결정문제에 답을 구하는 연산 : log(N)

도토리를 상자에 집어넣는연산 : K

 

시간복잡도 : O(Klog(N))이 된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/15732%20%EB%8F%84%ED%86%A0%EB%A6%AC%20%EC%88%A8%EA%B8%B0%EA%B8%B0/main.cpp

devxb/JJUNalgo