[python/알고리즘] 계란 낙하 실험 문제

 

계란을 낙하시켜 계란이 깨지는 높이를 찾아보자

---

 

Q1. 계란을 땅에 낙하하는 실험을 할 때, 계란이 깨지는 최소 높이(H)를 구하시오. 단, 계란은 1개 있음.

A. 

  
  # 계란 낙하실험 문제
  n = 100  # 횟수
  answer = random.randint(1, n)  # 높이

  # 계란이 깨지는지 안깨지는지 판별
  def isSafe(h):
      if h < answer :
          return True
      return False

  # 계란이 1개일 때, 순차탐색(1부터 100(n)까지)
  def eggDrop1(n):
      for height in range(1, n+1):
          if (not isSafe(height)):
              return height

  print(answer, eggDrop1(n))
  

-> 높이 1부터 100까지 순차적으로 확인한다. (순차탐색)

 

Q2. 계란을 땅에 낙하하는 실험을 할 때, 계란이 깨지는 최소 높이(H)를 구하시오. 단, 계란의 갯수는 무한.

A. 

  
  def eggDrop2(n):
      start = 1
      end = n
      while start + 1 < end :
          mid = (start+end) // 2
          if isSafe(mid):
              start = mid
          else:
              end = mid
      return end

  print(answer, eggDrop2(n))
  

-> 1부터 100까지의 범위를 나누어서 계란이 깨지는 최소 높이를 구한다. (분할탐색)

 

Q3. 계란을 땅에 낙하하는 실험을 할 때, 계란이 깨지는 최소 높이(H)를 구하시오. 단, 계란의 갯수는 2개가 있다.

A. 

  
  import math

  def twoEggsDrop(n):
      sqrt_n = math.floor(math.sqrt(n))
      for h in range(sqrt_n, n+1, sqrt_n):
          if not isSafe(h):
              break
      for h2 in range(h - sqrt_n+1, h):
          if not isSafe(h2):
              return h2
              
  answer = random.randint(1, 100)
  print(answer, twoEggsDrop(n))
  

 

 

 

 

출처 : Youtube 주니온TV 아무거나연구소의 코린아, 코딩하자! with 파이썬