이 문제 그리디로 풀면 왜 시간초과 나나요?
아직 점령되지 않은 섹터를 찾아서 해당 섹터에 대해 양옆과 위를 살펴봐서 점령할 곳이 없으면 점령 안하고 있으면 하는게 이득이니까 한부대의 수와 가장 가까운 곳을 점령해나감. (한 부대가 150이고 현제 섹터에 적이 100명이 있을 때, 위에 40,양 옆에 30명씩있으면 무조건 더 많은 곳을 점령하는게 최적, 따라서 위를 점령한다.) 이렇게 풀면 최악의 경우 한칸씩 점령해나간다고 쳐도 2*n번만에 답을 내지 않나요? 틀렸습니다가 나올지언정 시간초과가 왜날까요?
그 그리디 풀이가 최적인 걸 증명 못하면 틀린 풀이임. 그리디가 최적처럼 보여도 전체적인 모양이 다른 부대가 점령하는 걸 막아서 틀린 풀이가 될 수 있음. 근데 시간초과 어케냈누 ㄷㄷㄷㄷㄷ
아 덕분에 어떤 케이스인지 알겠습니다. 예를 들어 현재 섹터의 두칸 옆의 섹터가 점령할 수 있는 유일한 곳이 가운데 섹터였는데 그걸 현재 섹터가 최솟값이라고 가져가버리면 최적이 아니게 되는군요 그걸 두칸 옆의 부대한테 주고 나는 다른걸 고를 경우가 있기 때문에