ACM 10041, Vito's family

http://acm.uva.es/p/v100/10041.html  

1136046437_Vito Family2.cpp

1136046437_input.txt

1136046437_output.txt

이번 문제는 참으로 황당하지 않다 아니할 수 없다.

 

문 제에서 입력되는 번지에 집이 하나만 있다고 생각하여, set 자료 구조에 입력 값을 집어 넣는 바람에 해결 방법 자체가 틀렸기 때문이다. 다 푼 후에는 시간 초과까지 걸렸다. 여기에 특히 많은 시간이 걸렸다. 쉬운 문제라 생각하여 가볍게 풀어 보려 했는데 덕분에 많은 시간을 날려버렸다...

 

예 를 들어 1 1 8 이란 입력이 들어왔다고 하자. 이는 1번 거리에 친척이 2명 산다는 것을 의미한다. 따라서 비토가 1번 거리에 산다고 가정했을때, 친척 간의 이동 거리는 abs(1-1)+abs(1-1)+abs(1-8)=7이 된다. 또 다른 예로 비토가 4번 거리에 산다고 가정하자. 이때는 abs(4-1)+abs(4-1)+abs(4-8)=10이 된다.

 

다 른 예를 들어보자 1 2 7 10 10 의 입력이 있다. 이때 중간 주소를 x(예를 들어 6)라고 하자. x에서 좌측에 있는 집의 각 거리는 (x-2)+(x-1)이다. 우측 집과의 각 거리는 (10-x)+(10-x)이다. 이렇게 구한 값을 모두 더하면 x에서의 모든 집과의 거리 합이 된다. 정리해보자.
        
왼쪽 집과의 거리 = (x-2)+(x-1) = 2x-3
우측 집과의 거리 = (7-x)+(10-x)+(10-x) = 27-3x
        
위 식을 정리하면 2x-3+27-3x = 24-x가 된다. 집 개수가 변경되지 않는 한 x 값만 대입하여 거리를 구할 수 있다.         
양쪽의 집 개수가 같다면 x = 0이 되고 상수만 남는다. 따라서 주소가 달라져도 거리는 바뀌지 않는다.