2개의 계란

출처 : https://level.goorm.io/exam/43260/2%EA%B0%9C%EC%9D%98-%EA%B3%84%EB%9E%80/quiz/1

구글,아마존,MS 등의 기업 문제에서 나왔다고 하는데요...

문제가 재미있어서 풀어 보게 되었습니다.

 

문제풀이)

계란이 여러개 있다면 이진탐색으로 해법을 찾아 나가면 아주 간단한 문제였습니다.

만약 100층 건물이라고 한다면 50층 25층 13층 7층 4층 2층 1층 절반씩으로 나누어서 깨지면 절반 아래로 안 깨지면 절반 위로 올라가면서 떨어뜨려 보면 7번 만에 어디서 깨지는 지를 찾을 수 있는 문제였습니다.

 

그런데 예제 데이터를 보니 10 -> 4, 100->14 

문제를 자세히 살펴 보니 2개의 계란이라는 조건이 붙어 있습니다.

만약 50층에서 떨어뜨렸을때 깨진다면 남은 한개를 가지고 1층 부터 49층까지 올라가면서 떨어 뜨려 보면 최악으로 50번이 나오는 것을 확인 할 수 있었습니다.

 

그래서 다시 한번 생각을 하기로 했습니다.

10-> 4 가 나오는 이유는 4층(1회)에서 떨어 뜨려 보고 깨지면 남은 계란으로 1층부터 3층까지 검사해 보면 됩니다.

4층에서 깨지지 않으면 7층(2회)으로 올라가서 떨어뜨려 봅니다. 깨진다면 남은 계란으로 5층부터 6층까지 검사해 보면 4회 안에 해결 됩니다.

7층에서 깨지지 않으면 9층(3회)으로 올라가서 떨어뜨려 봅니다. 깨진다면 남은 계란으로 8층을 검사해 보면 됩니다.(4회 해결)

깨지지 않았다면 마지막으로  10층에서 검사하면 됩니다.

 

이렇게 생각을 하다 보니 이런 결과가 나오네요....

4회로 검사할 수 있는 층수는 1 + 2 + 3 + 4 = 10 이라는 결론이 나오네요.

그래서 이것이 맞는지 검증을 해 보기로 했습니다.

100층을 검사하기 위해 14회가 나온다고 하니...

14층에서 떨어 뜨려 보고 그 다음 27층 그 다음 39층 그 다음 50층-> 60층 -> 69층 -> 77층 -> 84층 -> 90층 -> 95층 -> 99층 -> 102층 -> 104층 -> 105층 

14회로는 105층 까지 검사를 할 수가 있었습니다.^^

코드를 구현해 보면 다음과 같습니다.

 

#include 
using namespace std;
int main() {
int num;
int cnt=1;
int sum=0;
cin >> num;
while(sum<num)
{
sum+=cnt++;
}
cout << cnt-1;
return 0;
}