4
10
10
10
100
일때 180이 나와야 합니다.
1715번 - 카드 정렬하기
쉬운듯 하면서도 어려운 문제이네요.
처음에는 배열에다 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를 써서하시면 정말 간략한 알고리즘을 구현하실수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
dhrhd080 5년 전
다른 글에서 찾아봤는데 10 10번 입력하면 340 제대로 나오고요
1입력하면 0출력합니다 계속 틀리게 나오는데 뭐가 문제일까요?