U E D R , A S I H C RSS

금고/하기웅

잡담

오호 역시 쉬운 문제가 아니었군~
대충은 나온다만... 사이트가서 보니 삼분법이 빠르니.. 이분법이 최적이란걸 증명을 못한다느니 그러네..ㅋㅋ
빡신 문제구만..^^ 이중 다이내믹이라나 뭐라나...ㅜㅜ; 뭐 조합론을 쓰면 뭐가 빠르니..ㅋㅋ 머리 아퍼..ㅋㅋ

지금보니 생각할게 많네..ㅡㅡ; 금고를 떨어뜨렸을 때 깨진 경우 안깨진 경우에 따라서 다음에 할 수 있는 작업이 틀려지고..
이거 지대 복잡하네..ㅡㅡ;
오늘 하루 종일 삽질이여...ㅡㅡ;

소감

너무 쉽게 나오는데 잘못한 건가~??
일단 f층에서 s개의 금고가 있으면 s-1개는 f층의 반, 또 그기의 반 이렇게 떨어뜨려보면 되고
마지막 한개는 그렇게 해서 좁혀진 공간에서 제일 낮은데 부터 하나하나 떨어뜨려보면 된다고 생각했는데.
그래서 나온 식이 floor/2^(s-1)+s-1임~

그리고 혹시나 floor/2^s이 1보다 작아 질때는 s번을 떨어뜨려 볼 필요가 없기때문에
s를 감소 시켜가며 floor/2^s가 1보다 커거나 같아질때 s+1을 리턴하면 된다.

s(금고)가 충분하다고 했을 경우를 생각해보면...
7일때, 7이라고 하면 4에서 한번 6에서 한번 7에서 한번이면 3번에 찾아지는데.
8일때, 8이라고 하면 4에서 한번 6에서 한번 7에서 한번 8에서 한번 4번에 찾아진다.
2의 지수승에서 부터 하나가 많아진다.
8은 2^3이고 지수에 1을 더한 4번이 최소횟수가 된다.
9일때 9라고하면 그때도 4회가 된다 (16이 될때 까지)

즉, floor/2^s가 1보다 커지는 순간 s+1회 임을 알 수 있다.

소스

~cpp
#include <iostream> 
#include <cmath> 
using namespace std; 

int testcase, nFloor, nSaver; 

int calculate(int f, int s) 
{ 
	if(f/pow(2,s)<1)
	{
		while(s--)
		{
			if(f/pow(2,s)>=1)
				return s+1;
		}
	}
    return f/pow(2,s-1)+s-1;   // f/pow(2,s-1) =>s-1번을 통해 나뉘어지고 난 후에 그 부분의 최소횟수
} 

int main() 
{ 
    cin>>testcase; 
    while(testcase--) 
    { 
        cin>>nFloor>>nSaver; 
        cout << calculate(nFloor, nSaver) <<endl; 
    } 
    return 0; 
} 
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:46
Processing time 0.0198 sec