yukariko   2년 전

K개를 일단 받아온다음

그 다음 요소부터는 그리디 방식으로 중간에 삽입할때 최소가 나오는경우를 찾아서 넣었는데

그리디로는 해결이 불가능한 건가요??

제 식 어딘가가 틀린거같은데 찾질 못하겠어서 질문드립니다..

appa   2년 전

저는 사람들 키 중에서 가장 큰 값과 가장 작은 값(Hmin, Hmax), 사자 키 중에서 가장 큰 값과 가장 작은 값(Lmin, Lmax), 인접한 사자들 사이의 키 차이의 합(S). 총 3개의 값만 가지고도 답을 구할 수 있었어요. 그런데 가장 작은 사자가 맨 앞이거나 맨 끝, 가장 큰 사자가 맨 앞이거나 맨 끝인 경우에는 특별히 예외 처리를 해야하더라구요.

일반적인 경우에(Hmin<Lmin이거나 Hmax>Lmax인 경우 중)는 가장 작은 사자 옆에 가장 작은 사람을 배치할 때, 키가 내려갔다가 올라와야해서 차이의 곱하기 2 값의 값을 S에 더해주어야하는데 가장 작은 사자가 사자 중에서 맨 앞이거나 맨 끝이라면, 곱하기 2가 아니라 그냥 그 차이를 더해주어야했어요. 가장 큰 경우도 마찬가지구요.

그 부분도 고려해주셨나 궁금하네요.

yukariko   2년 전

[email protected] 님이 말씀하신 풀이랑 좀 달라서 처리가 제대로 됬는지는 모르겠네요..

그런데 가장 큰 값과 작은 값으로만 문제 해결이 가능하다는 말을 들으니 뭔가 감이 잡혔습니다.

답변 감사합니다!

yukariko   2년 전

어디가 틀리는걸까요 ㅠㅠ

appa   2년 전

hmin < lmin인 경우에 (lmin - hmin) * (a[0] == lmin || a[K-1] == lmin ? 1: 2)과 a[0]-hmin과 a[K-1]-hmin 셋 중에서 최솟값을 res에 더해주면 맞을거에요.

hmax > lmax인 경우에는 마찬가지로 고려해주신 것과 hmax-a[0]과 hmax-a[K-1] 셋 중에서 최솟값을 res에 더해줘야하구요.

yukariko   2년 전

헉..

뭔가 전부 도움을 받았지만.. 일단 AC는 받았습니다.

이게 그러니까 사람의 최소는 사자의 최소주변에 놓는것 * 2보다 그냥 맨 앞, 맨 뒤에 놓는것이 더 좋을수도 있다 라는 의미인거죠?

그리고 그런 경우는 사람의 최소나 최대만 고려해주면 되는것이고..

ㅠㅠ 사자의 최소 최대만 머리에 들어있다보니 그런 경우를 고려하지 못했네요.

appa   2년 전

네ㅎㅎ 그런데 유라리코님이 처음 접근하신 방법대로 푼 분들도 계신걸로 알고있어요. nanami님의 소스를 참고하시면 될 것 같아요.

yukariko   2년 전

그렇네요.. nanami님 또한 사람의 최대,최소 를 구한것이 저와 다르긴 하지만

넣을 위치를 찾아주는 방법이 제가 생각한것과 유사해 보입니다.

역시 아직 갈길이 멀군요 ㅋㅋ..

친절한 답변 감사합니다!

amugeona   2년 전

사자 가족의 최대 / 최소 범위 이내의 원소들은 제거해줘도 됩니다.

그리고 다른 사람들의 최대 / 최소값을 배치하게 되면, 범위 밖의 사람들은 이 라인에 환승(?)하면 되므로 결국 이 문제는 다른 사람들 중 최대 / 최소값을 어디에 배치하냐 하는 문제입니다.

그래서 이거만 처리해주면 정답 나오실겁니다.(?)

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