Maintenance script: Repair batch-0004 pages from live compare

2026-03-27T00:37:16Z

Repair batch-0004 pages from live compare

← Older revision		Revision as of 00:37, 27 March 2026
Line 1:		Line 1:
	== 잡담 ==		== 잡담 ==
	오호~~ 역시 쉬운 문제가 아니었군~~~~~~~		오호~~ 역시 쉬운 문제가 아니었군[[User:Maintenance script\|Maintenance script]] ([[User talk:Maintenance script\|talk]])
	대충은 나온다만... 사이트가서 보니 삼분법이 빠르니.. 이분법이 최적이란걸 증명을 못한다느니 그러네..ㅋㅋ		대충은 나온다만... 사이트가서 보니 삼분법이 빠르니.. 이분법이 최적이란걸 증명을 못한다느니 그러네..ㅋㅋ
	빡신 문제구만..^^ 이중 다이내믹이라나 뭐라나...ㅜㅜ; 뭐 조합론을 쓰면 뭐가 빠르니..ㅋㅋ 머리 아퍼..ㅋㅋ		빡신 문제구만..^^ 이중 다이내믹이라나 뭐라나...ㅜㅜ; 뭐 조합론을 쓰면 뭐가 빠르니..ㅋㅋ 머리 아퍼..ㅋㅋ

imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:46Z

New page

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

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

== 소감 ==
너무 쉽게 나오는데 잘못한 건가~??
일단 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회 임을 알 수 있다.

== 소스 ==
#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;
}

금고/하기웅 - Revision history

Maintenance script: Repair batch-0004 pages from live compare

imported>Unknown at 05:28, 7 February 2021