[Hard] Reflections

mirrorX 를 이용할 때는 y, z 좌표가 바뀌지 않는다. mirrorY 와 mirrorZ 에 대해서도 같은 식으로 된다. 따라서 x좌표의 이동, y좌표의 이동, z좌표의 이동을 각각 따로 볼 수 있다. solve(mirrors[], target) 같은 함수를 만들어서 x좌표, y좌표, z좌표에 대해 각각 불러주면 된다. 몇가지 더 관찰해야하는 성질이 있다. - 각 거울은 최대 한번만 사용하는 것이 좋다. - 내가 현재 좌표a에 있고, 좌표m에 있는 mirror를 이용한다면 2*m - a 로 이동하게 된다. 내가 거울의 왼쪽에 있든 오른쪽에 있든 상관없다. - normal move 를 한 후 mirror 를 이용하는 것과 그 반대는 차이가 없다. mirror 가 한 개 있을 때를 먼저 증명한 후, 그걸 여러개 이용하는 것을 생각하면 된다. 이 성질들을 이용해 풀이를 만들어보자. m개의 mirror 가 X[1], X[2], ..., X[m] 에 위치해있다고 해보자. 이 mirror 들을 전부 다 사용하고 마지막에 normal move 를 수행해서 0에서 출발해 목적지까지 최소비용으로 이동하려고 한다. mirror 를 이용하는 순서를 a1, a2, ..., am 이라고 하면 처음 mirror 를 이용하면 2*X[a1] - 0 그다음 mirror 를 이용하면 2*X[a2] - (2*X[a1] - 0) 그다음 mirror 를 이용하면 2*X[a3] - (2*X[a2] - (2*X[a1] - 0)) ... 이런 식이 된다. mirror 를 전부 이용하고 나면 좌표는 2*(X[a]+X[b]+X[c]+...) - 2*(X[p]+X[q]+X[r]+...) 와 같은 형태가 된다. 그리고 (+항에 있는 X의 개수) - (-항에 있는 X의 개수) == 0 or 1 을 만족해야 한다. 그 후에 마지막으로 normal move를 사용하면 총 비용은 |(2*(X[a]+X[b]+X[c]+...)-2*(X[p]+X[q]+X[r]+...)) - (목적지 좌표)| + (+항에 있는 X의 개수) + (-항에 있는 X의 개수) 가 된다. k <= (n+1)/2 인 k에 대해, mirror 를 k개 고르는 경우를 모두 순회하면서 X의 합을 저장해 bucket[k] 에 다 넣고 정렬해둔다. bucket[k] 의 원소 하나를 sumA 라고 하고 이걸 +항의 합이라고 하자. -항의 합 sumB 는 bucket[k] 나 bucket[k-1] 에서 고를 수 있고 |(2*sumA - 2*sumB) - (목적지 좌표)| 이 최소가 되도록 골라야 한다. 이것을 이분검색으로 찾든 two pointer 로 찾든 하면 된다. sumA를 구성하는 집합과 sumB를 구성하는 집합이 서로소가 아닐 수도 있지 않냐! 라고 생각할지도 모르지만 만약 두 집합에 공통인 원소가 존재하면 그 때의 답은 무조건 최적이 될 수 없다. 따라서 그냥 저렇게 돌려도 상관없다. 전체 시간복잡도는 O(2^n * n)