그래요?? 이게 왜 틀렸을까요? 맞왜틀이군요.
배열이 대충 이런 식으로 있다고 합시다.
arr = [1, 1, 100만, 1, 1, 3, 4, 5, 3, 3]
이 때 s = 0이고, e = 9이므로, mid = 4일 겁니다. 그러면 gu님의 알고리즘에 따르면
arr = [1,1, 100만, 1, 1, 3, 4, 5, 3, 3]
le ^ ^ ri
가 될 겁니다. gu님의 알고리즘에 따르면 왼쪽에 있는 것보다 오른쪽에 있는 게 더 크면 무조건 우측에 있는 걸 뽑고 아니라면 왼쪽에 있는 걸 뽑는데..
Sum = 30이라고 해 봅시다. 그러면 일단 arr[le]<arr[ri]니까 ri를 뽑아요. 그러면 ri가 하나 증가하겠죠?
다음에도 arr[le] < 5이므로 우측 것을 뽑아요.
왜? arr[le]의 값은 1인데, x>=5인 경우, arr[x]>1이기 때문입니다.
그러면 계속 오른쪽 것만 뽑다 끝날 건데..
사실 중간에 걸쳐 있을 때, 최적의 해는 오른쪽 것만 계속 뽑는 것이 아닙니다.
gustjq1101 4년 전
분할정복으로 푼 코드 입니다.
코드에서 어느부분이 틀린지 전혀 감을 못잡겠습니다. ㅜㅜ
투포인터를 이용해서 맞춘 코드가 있어서 스캐폴딩을 해서 반례를 찾아보니
n = 10, s = 33961, v = {3446, 7276, 7627, 937, 9550, 1712, 3495, 2909, 4668, 5230}
my result = 8 correct result = 7
가 나왔습니다.