[백준 16198] 에너지 모으기 - Java

그리디로 풀 수 있을 줄 알았는데, 예외가 있나 봅니다. 그냥 완전탐색으로 푸는 법뿐인가요?

항상 구슬 무게의 최댓값일 선택하고 왼쪽이나 오른쪽의 구슬을 제거하는 방식으로 수행하면, 최댓값이 항상 곱해지므로 최댓값이 나온다고 생각했습니다. 하지만 지금 글을 쓰면서 예외가 몇 가지 생각이 나네요,,, 2*3이 1*4보다 클 테니까요,,,하,,, 헤매느라 괜히 시간만 많이 잡아먹게 되었습니다.Design그리디로 풀 수 있을 줄 알고 아래와 같이 설계했고, 위에서 틀린 이유를 적었습니다.

아무튼 참고만 하시길 바랍니다. 그리고 오기를 부려 한 번 탐색할 때마다 에너지의 최댓값을 구하는 방식으로도 구현했으나 틀렸다고 합니다.

예제에..........