kkw564   2년 전

맵을 이용해서 문제를 풀어보고자 했습니다.

인풋은 내림차순으로 정렬하여 큰 물건부터 상자에 넣기 시작했고, 아래 알고리즘을 설명하고 있습니다.


chogahui05   2년 전

숌은 짐을 챙겨서 겨울캠프에서 집으로 가려고 한다. 

근데 숌은 공부를 많이 하러 캠프에 온 것이기 때문에 책을 엄청나게 많이 가지고 왔다. 숌은 이 책을 방에 탑처럼 쌓아 놨다.

숌은 책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다. 

책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.


이것 때문에 안 되지 않을까요?

kkw564   2년 전

저 말로 인해 책을 원래는 가장 위에 책부터 넣어야하는데

정렬을 통해 미리 어떻게 넣을지 생각을해둘 수 있다고 가정할 수 있지 않나요?


예를들어

6 10

2 3 4 5 6 7인경우


정렬을 하지 않고 위 책부터 넣는다고 가정하면 

2 3 4 / 5 / 6 / 7 로 총 4개의 박스를 이용해야 하는데


정렬을 하고 넣으면

7 3 / 6 4 / 5 2 로 총 3개의 박스를 이용할 수 있게 된다고 생각했습니다.

즉, 2 3 4 5 6 7로 넣는다 해도

2 넣고

3을 다른 박스에 넣는거죠 7이 올것을 이미 알고있기에

그리고 4도 다른 박스에 넣고

5를 2박에서 넣어 2 5 / 3 / 4가 되고

6을 4박스에 넣어 2 5 / 3 / 4 6이 되고

마지막 7을 3박스에 넣어 2 5 / 3 7 / 4 6이 된다고 생각했습니다.


제가 잘못생각하고있는걸까요..?

kkw564   2년 전

정말 혹시나 해서 그냥 그리디.. 제일 기본적인 그리디를 이용하니 ac를 받네요...

맞고도 왜 맞는지 모르겠습니다.. 해석의 차이가 있을 수 있다고 생각드는데 저만 그런건지도 궁금하네요

chogahui05   2년 전

그림이라도 그려져 있다면 좋겠네요..

혹은 인풋 케이스를 조금 더 추가해서 설명을 해 주시거나..


그런데 사실 맨 위부터 쌓아져 있기 때문에

1 2 3 4 5 6 7 이렇게 있다고 가정하면

1 2 3 / 4 / 5 / 6 / 7

이런 식으로는 넣을 수 있을 겁니다.. 엄청나게 밑에 있는 책을 빼기에는

위에 있는 책들이 너무 무거워서 못 하는 것일지도 모르지요.. 이분탐색에서 f(x)를 세울 때

내부적으로 이런 처리를 하는 경우가 많긴 하더라고요..

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