저는 사람들 키 중에서 가장 큰 값과 가장 작은 값(Hmin, Hmax), 사자 키 중에서 가장 큰 값과 가장 작은 값(Lmin, Lmax), 인접한 사자들 사이의 키 차이의 합(S). 총 3개의 값만 가지고도 답을 구할 수 있었어요. 그런데 가장 작은 사자가 맨 앞이거나 맨 끝, 가장 큰 사자가 맨 앞이거나 맨 끝인 경우에는 특별히 예외 처리를 해야하더라구요.
일반적인 경우에(Hmin<Lmin이거나 Hmax>Lmax인 경우 중)는 가장 작은 사자 옆에 가장 작은 사람을 배치할 때, 키가 내려갔다가 올라와야해서 차이의 곱하기 2 값의 값을 S에 더해주어야하는데 가장 작은 사자가 사자 중에서 맨 앞이거나 맨 끝이라면, 곱하기 2가 아니라 그냥 그 차이를 더해주어야했어요. 가장 큰 경우도 마찬가지구요.
그 부분도 고려해주셨나 궁금하네요.
yukariko 9년 전
K개를 일단 받아온다음
그 다음 요소부터는 그리디 방식으로 중간에 삽입할때 최소가 나오는경우를 찾아서 넣었는데
그리디로는 해결이 불가능한 건가요??
제 식 어딘가가 틀린거같은데 찾질 못하겠어서 질문드립니다..