랜덤으로 케이스를 만들어서 돌려봤는데 반례를 찾았습니다

(케이스 더러워서 죄송합니다)

틀린 해법입니다. {1, 3, 3, 3, 4, 4}가 주어질 경우 {1, 4, 4}와 {3, 3, 3}으로 분할하는 것이 최적이지만, 제시하신 해법에서는 반드시 두 개의 4를 다른 그룹에 분배하게 됩니다.

해당 문제는 partition problem의 한 변형으로, NP-hard임이 알려져 있습니다. 다만 주어지는 수의 크기에 의존하는(pseudo-polynomial) 비교적 간단한 dynamic programming 해법이 있으며, 지금까지 푸신 문제 중에도 이와 비슷한 느낌의 문제가 있었을 거라고 생각합니다.

powerkim님은 '대부분 경우'라는 말을 하셔서 반례가 아니고 Greedy할 때 얼마나 근사적으로 답을 찾을 수 있는지 물어보시는 것 같긴 하네요

문제가, Given an array consisting of N Numbers.
Divide it into two Equal partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum. 인데,

일단 풀이는 구글에 tug of war problem 검색해보시면 풀이는 꽤 많고 

이러한 유형이 partition problem으로 불리는 것 같은데 partition problem은 NP-완전문제로 알려져 있다는듯 합니다.

powerkim님의 풀이가 LPT 알고리즘에 가깝다는 생각도 드네요

배열 크기가 안 정해져 있을 때는, Greedy한 방법이 approximation ratio가 7/6라고 하네요. https://talzuchung-kty.tistory.com/10?category=843612

답변주신 세 분 모두 감사합니다!

사실 저는 이 문제가 greedy로 풀어야 하는 문제인줄로만 알았습니다.. 그래서 관련된 문제를 검색할 때도 greedy 관련 키워드로만 검색을 해서 도저히 찾을 수 없었는데

세 분 덕분에 위 해법이 틀렸고, 어떠어떠한 반례들이 있는지 알 수 있었으며 어떠한 방식으로 접근해야 풀 수 있는지도 알 수 있게 되었습니다. 감사합니다!