[Swift 알고리즘] LeetCode 1884. Egg Drop With 2 Eggs and N Floors

×

Math, Dynamic Programming | Medium

LeetCode 1884. Egg Drop With 2 Eggs and N Floors

뭐라는겨,,, 

이해하는 데 오래걸렸다. 

구간을 나눠서 계란이 확실히 깨지는 층수를 찾는다는 것 까지는 이해를 했는데... 

예를 들어 10으로 나누면 10, 20 ... 100 까지 10번 던진 후, 100에서 깨지면 91~99 까지 9번을 더 던져 최소 19번을 던져야 한다. 

구간을 다른 수들로 나눠도 다 19번이 나오는데 어떻게 답이 14가 될 수 있는거지??? 😮

 

요 영상보고 겨우 이해함 ㅎ

https://youtu.be/NGtt7GJ1uiM

핵심은 구간을 일정하게 나누는 것이 아니라, 위로 올라갈수록 구간을 줄여가는 것! 

크... 

식을 세우면 n + (n-1) + (n-2) + ... + 1 >= 100 인 n을 찾으면 된다. 

따라서 100 층에서 계란이 깨지는 층수를 확실하게 알아내기 위해서는 최소 14번을 던져야 한다. 

 

dp 문제라고 해서 무식하게 배열에 하나씩 넣어가며 내가 처음에 푼 방식,,

func twoEggDrop(_ n: Int) -> Int {
    var dp = [0]
    var result = 0
    while result < n {
        result = dp[dp.count - 1] + dp.count
        dp.append(result)
        print(dp)
    }
    return dp.count - 1
}

이거는 배열 사용하지 않고 그냥 변수 두 개와 덧셈만 이용해서 풀어서 더 간결하고 효율적이라 생각하는 답안.  

func twoEggDrop(_ n: Int) -> Int {
    var step = 0, drops = 0
    while drops < n {
        step += 1
        drops += step
    }
    return step
}