마구간 질문드립니다

Question

안녕하세요 선생님, 마구간 문제 관련하여 잘 이해가 되지 않는 부분이 있어 이렇게 글 남겨드립니다.   count 함수를 통하여 말의 개수를 셀 때, 좌표의 가장 왼쪽, 즉 좌표 배열을 arr이라고 하면, 선생님께서는 count 함수에서 말의 개수를 세실 때, arr[0]을 ep로 두어 for문으로 문제를 해결하셨는데요, 이 부분이 직관적으로 확 와닿지 않습니다 ㅠㅠ.. 마땅한 반례를 찾지는 못하였으나, arr[0] 이외의 부분에서 답이 있을 수 있으니, ep를 이중 for문으로 돌려 찾아야 하는 것이 아닌가 생각이 드는데, 그렇게 하지 않으신 이유에 대하여 질문 남겨드립니다   감사합니다 선생님!

김태원 · Answer

안녕하세요^^ 사실 직관적인 건데요. 가장 왼쪽 마굿간(arr[0])부터 가장 오른쪽 마굿간으로 가면서 말을 배치할 때 최대한 말을 많이 배치하려면 가장 왼쪽 즉 첫번째 마굿간에 무조건 먼저 말을 배치하고 시작해야 제일 좋은 최적을 경우입니다. 가장 왼쪽 첫번째 마굿간에 말을 배치한다고 해서 그 다음 마굿간에 말을 배치하는데 더 악영양을 끼치는 경우는 존재하지 않습니다.