naegeora   5달 전

동적계획으로 풀었는데 시간초과가 납니다...

시간을 줄이려고 Memo하려고 하니...배열갯수가 너무나 크네요...2억7개 계단이라서

배열 잡기도 어렵네요...

다른 방법이 없을까요?

동적계획 로직은

i개의 계란으로 j층에서 떨어뜨릴때의 경우의수  f(i,j): 

k층에서 시도시  깨졌을때는 i-1개를 가지고 k-1층에서 시도(아랫방향)와 (윗방향)  i개를 가지고 j-k층에서 시도수의 max값. (k=1에서 j까지)
Math.min(temp,1+Math.max(f(i-1,k-1), f(i,j-k)));초기화:계란1개가지고떨어뜨릴때는 return 층수



zlzmsrhak   5달 전

이 풀이보다 더 좋은 시간복잡도를 가지는 풀이가 있습니다.

다른 알고리즘을 생각해보세요.

naegeora   5달 전

zlzmsrhak   님 답변 감사합니다.

아무리 생각해도 나은 알고리즘 찾기가....? 흰트를 줄수 없으신가요?

댓글을 작성하려면 로그인해야 합니다.