dhrhd080   5년 전

다른 글에서 찾아봤는데  10 10번 입력하면 340 제대로 나오고요

1입력하면 0출력합니다  계속 틀리게 나오는데 뭐가 문제일까요?

klimmek55   5년 전

4
10
10
10
100

일때 180이 나와야 합니다.

midascha   2년 전

쉬운듯 하면서도 어려운 문제이네요.

처음에는 배열에다 input data를 넣고 내림 차순 정렬을 한번만하면 될 줄알고

맞겠지 하고 제출하니 제출하자만 fail이 떠서 당황했었습니다.

결과값을 타입을 int에서 long long으로 바꿔도 보고 다양한 반례도 찾아서

해 보았는데, 어떤 경우는 맞고 어떤 경우는 틀리는 경우가 있어서 문제를 처음부터

다시 찬찬히 봤었는데 제시된 input으로만 생각한게 패인이었습니다.

제시된 input은 10, 20, 40 이기 때문에 10+20 = 30이므로 30+40하면 크게 문제가 없습니다.

그러나, 10, 10, 10, 10 인경우에는 10+10 = 20한거와 20+10하면 최소수가 안나오게 됩니다.

즉, 처음 더한 수와 남아 있는 수의 최소값으로 다시 더해야 하므로, 처음에 더한 수 20은 최고로 뒤로

보내고 다시 남아 있는 수 10+10=20을 한 다음에 다시 내림차순 정렬해서 20 + 20=40 한 다음에

모든 수를 더해야 합니다.

결론 priority_queue를 써서하시면 정말 간략한 알고리즘을 구현하실수 있습니다.

midascha   2년 전

제일 좋은 반례는 아래의 10이 10개 있는 경우인데 340이 정답입니다.

10

10

10

10

10

10

10

10

10

10

10

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