[Leetcode] 1217. Minimum Cost to Move Chips to The Same Position

문제 : https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position/

---

n의 크기인 position 1차원 배열이 있다. position[i]는 i 번째 칩의 위치를 의미한다.

한 번에 i 번째 칩의 위치를 왼쪽이나 오른쪽으로 두 칸 움직이는 비용은 0이고, 한 칸 움직일 때는 1의 비용이 든다.

모든 칩을 동일한 위치로 옮기려고 할 때 필요한 최소 비용을 구하라.

---

2만큼 움직이는건 비용이 들지 않으므로 짝수번 움직이는건 비용이 들지 않는 것과 같다.

따라서 0 비용으로 짝수번째 위치에 있는 칩들은 2번으로, 홀수번째 위치에 있는 칩들은 1번으로 먼저 옮긴다.

그리고 짝수, 홀수에 있는 칩들 개수 중 더 작은 개수의 칩들을 반대편으로 옮기면 정답이 되므로, 짝수, 홀수 위치의 칩들 개수 중 최소값이 정답이 된다.

 

시간복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1217.%20Minimum%20Cost%20to%20Move%20Chips%20to%20The%20Same%20Position.cpp