강의실/정보영재

출처 : 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;
}

 

 

7 0
  • 청결원 2019.05.10 16:30    

    포스팅 잘 보고 가네요
    오늘 하루 마무리 잘 하세요~

  • 유하v 2019.05.11 00:30 신고    

    해설을 보지 않으면 못풀겠는걸요ㅎㅎ;;

  • 버블프라이스 2019.05.11 04:40 신고    

    2개의 계란 문제이군요?
    어렵네요.. ㅎㅎ 즐거운 주말 보내시길 바래요

  • *저녁노을* 2019.05.11 05:41 신고    

    ㅎㅎ어렵군요.

    잘 보고 갑니다.

    즐거운 주말 되세요^^

  • 핑구야 날자 2019.05.11 06:42    

    독특한 문제네요 덕분에 저도 재미있게 잘 보고 갑니다

  • 공수래공수거 2019.05.11 10:45 신고    

    알아두면 좋을것 같네요.
    이런 예제를 많이 풀어야 합니다.^^

  • 휴식같은 친구 2019.05.13 12:16 신고    

    아려운데요...ㅎㅎ
    논리력 끌어내려면 짱구 열심히 굴려야겠어요.
    잘 보고 갑니다.