안녕하세요

 

혼자서 알고리즘 공부하다가 한 예제를 찾은게,

 

N개의 요소를 가진 circular array를 M개의 group으로 이웃한 것들끼리 묶었을 때 (안묶이는 요소가 없이 모두 묶어야함),

M개의 group 중 group내 합이 가장 큰 값이랑 작은 값의 차가 최소가 되게 묶은 경우 그 최소의 값을 구하여라.

 

라는 문제가 있는데

 

예를 들어

circular array가

 

8 13 2 9 4

이며

 

M = 3 개의 group으로 묶는 경우

 

8 }  { 13 } { 2 9 } { 4

 

이렇게 묶어야 최대가 13, 최소가 11이 되어 13-11 = 2가 정답입니다.

 

 

이런 문제가 있는데 recursive로 풀면 답이야 쉽게 나오지만 (엄청난 시간복잡도.....)

dynamic programming으로 풀 경우 도저히 아이디어가 떠오르지 않네요

 

어떤걸 memo하고 어떤걸 for loop로 둬야할지....

 

greedy도 생각해봤는데 제일 큰 값을 중심으로 묶어나가는거는 너무 불안할거같기도하고요..

 

어렵네요ㅠㅠ