1. 개요
점들 사이에서 가장 가까운 거리를 추론하는 문제.2. 문제
5명의 친구들이 한 자리에서 모이기로 했다. 친구들의 위치는 아래와 같다.
친구들이 움직인 거리가 최소가 되도록 하려면 어디에서 만나야 할까?
| D | |||||
| B | |||||
| C | |||||
| E | |||||
| A |
친구들이 움직인 거리가 최소가 되도록 하려면 어디에서 만나야 할까?
3. 해답
- [해답 보기 / 접기]
- 안 유명한 듯 하면서도 은근히 여기저기서 보이는 문제 유형. 일단 가장 쉬운 풀이법은 아무데나 점을 하나 잡고 그 점을 움직이면서 몇 개의 점과 가까워지는 지 확인하는 것이다. 예를 들면 아래와 같은 지점을 찍어두고,
D B C X E A
이 X를 위나 아래, 왼쪽, 오른쪽으로 움직였을 때 몇 개의 점과 가까워지는지 확인하고 더 많은 점과 가까워지는 쪽으로 움직이면 된다. 위의 상황에서 X를 위로 움직이면 3개의 점과(B, C, D) 가까워지고 2개의 점과(A, E) 멀어지기 때문에 총 거리는 1 짧아지는 것과 마찬가지이다.
D B C X E A
이제 이 점을 왼쪽으로 움직이면 3개의 점과(A, B, C) 가까워지고 2개의 점과(D, E) 멀어지니 C와 같은 지점으로 X를 옮길 수 있다.
D B X(C) E A
이때 여기서 어느 쪽으로 X를 움직여도 멀어지는 점만 3개고 가까워지는 점은 2개밖에 되지 않는다. 따라서 C가 있는 지점이 친구들이 움직일 가장 거리가 짧은 지점이 된다.
좀 더 일반적인 풀이법으로는 행과 열의 거리를 분리하여 생각하는 것이다. 일단 행의 거리를 살펴보면
A B C D E
행 거리의 총합이 가장 짧은 지점은 중앙인 C이고
D B C E A
열 거리의 총합이 가장 짧은 지점도 C이다. 따라서 거리의 총합의 최소는 C가 되는 지점.
최단거리가 되는 지점이 2개 이상 나오는 것도 물론 가능하다. 행과 열이 같은 지점이 존재할 경우 자주 발생하는 편.