<div>안녕하세요</div> <div> </div> <div>혼자서 알고리즘 공부하다가 한 예제를 찾은게,</div> <div> </div> <div>N개의 요소를 가진 circular array를 M개의 group으로 이웃한 것들끼리 묶었을 때 (안묶이는 요소가 없이 모두 묶어야함),</div> <div>M개의 group 중 group내 합이 가장 큰 값이랑 작은 값의 차가 최소가 되게 묶은 경우 그 최소의 값을 구하여라.</div> <div> </div> <div>라는 문제가 있는데</div> <div> </div> <div>예를 들어</div> <div>circular array가 </div> <div> </div> <div>8 13 2 9 4</div> <div>이며</div> <div> </div> <div>M = 3 개의 group으로 묶는 경우</div> <div> </div> <div>8 } { 13 } { 2 9 } { 4</div> <div> </div> <div>이렇게 묶어야 최대가 13, 최소가 11이 되어 13-11 = 2가 정답입니다.</div> <div> </div> <div> </div> <div>이런 문제가 있는데 recursive로 풀면 답이야 쉽게 나오지만 (엄청난 시간복잡도.....)</div> <div>dynamic programming으로 풀 경우 도저히 아이디어가 떠오르지 않네요</div> <div> </div> <div>어떤걸 memo하고 어떤걸 for loop로 둬야할지....</div> <div> </div> <div>greedy도 생각해봤는데 제일 큰 값을 중심으로 묶어나가는거는 너무 불안할거같기도하고요..</div> <div> </div> <div>어렵네요ㅠㅠ</div> <div> </div> <div> </div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.