sgc109   7년 전

dp로 O(n^2) 인 알고리즘으로 AC 받긴했는데 사실 x 좌표로 정렬했을때 묶는 점들이 꼭 연속된게 아니라

중간에 어떤 점을 건너뛰고 묶었을때는 최선의 답이 나오지 않는 다는것이 직관적으로 맞을것같아서 구현했는데

정확히 증명은 하지 못했기에 질문드립니다. x축으로 정렬했을 때 최적 부분구조가 나오는지 증명하는 법(?)(맞나요?)을 가르쳐주시면 감사드리겠습니다.

koosaga   7년 전

어떤 최적의 해가 연속적으로 덮지 않고 띄엄띄엄 덮었다고 생각해봅시다. x축 정렬로 인덱스 매겼을 때 예를 들어 어떤 기지국 a가 1 3 4 6을 덮었다고 생각해봅시다. 

그러면 이제 어떤 다른 기지국 b가 2를 덮었을 겁니다. 

케이스가 두개입니다. 

1. a가 b보다 크다 : 그러면 이미 2가 a에 의해 덮여있을 겁니다. b를 쓸 이유가 없습니다. 

2. a가 b보다 작다 : 이 때 생각해보면, 1이나 3 4 6 둘 중 하나는 b에도 속해있습니다. 이러한 영역을 포기하고 b에게 넘겨줍시다. 1을 넘겨줬다고 합시다.  a에 있는 불연속한 구간을 적어도 하나 줄일 수 있습니다. (1 / 34 / 6이었으면 이제 34 / 6이니까) b에서는 불연속한 구간이 줄지 않습니다. (2에 붙어있던 덩어리니까)


반복해서 최적인 해의 비용을 증가시키지 않고, 최적해 하나를 연속구간으로 바꿀 수 있습니다. 고로 연속구간으로 덮을 수 있고 부분최적구조를 쓸 수 있습니다. 

sgc109   7년 전

@koosaga 감사합니다. 근데 위에서 말씀하신 케이스에서 b가 a 보다 작을 가능성이 있나요? 

koosaga   7년 전

없습니다 (그래서 없음 역시 증명했습니다)

sgc109   7년 전

@koosaga 아 ㅋㅋ 감사합니다 

댓글을 작성하려면 로그인해야 합니다.