C++로 풀어보는 칩 이동 최소 비용 문제

문제 설명

여러 개의 칩이 놓여 있고, i번째 칩은 현재 chips[i] 위치에 있다고 가정해 봅시다. 각 칩에 대해 다음 두 가지 연산을 원하는 만큼(0회 포함) 반복해서 수행할 수 있습니다.

i번째 칩을 왼쪽 또는 오른쪽으로 2칸 이동한다. 이때 비용은 0입니다.
i번째 칩을 왼쪽 또는 오른쪽으로 1칸 이동한다. 이때 비용은 1입니다.

처음에 주어지는 칩은 두 개 이상입니다. 모든 칩을 같은 위치로 모으는 데 필요한 최소 비용을 구해야 하며, 최종 위치는 어디든 상관없습니다. 예를 들어 초기 칩 배열이 [2,2,2,3,3]이라면 출력은 2가 됩니다. 네 번째 칩과 다섯 번째 칩을 각각 비용 1씩 들여 위치 2로 옮기면 되기 때문에, 전체 최소 비용은 2입니다.

해결 접근 방법

이 문제의 핵심은 비용 0으로 2칸씩 이동할 수 있다는 점입니다. 2칸씩 움직이면 위치의 홀짝성(짝수/홀수)은 변하지 않습니다. 따라서 같은 홀짝성을 가진 위치에 있는 칩들은 전혀 비용 없이 한곳에 모을 수 있습니다. 결국 비용이 발생하는 경우는 홀수 위치 그룹과 짝수 위치 그룹 중 한쪽을 다른 쪽으로 옮길 때뿐이며, 이때 칩 하나당 비용 1이 듭니다.

따라서 다음 단계로 문제를 해결할 수 있습니다.

odd := 0, even := 0으로 초기화합니다.
배열 전체를 순회하면서 chips[i]가 홀수이면 odd를, 짝수이면 even을 1씩 증가시킵니다.
odd와 even 중 더 작은 값을 반환합니다.

C++ 구현 예제

더 나은 이해를 돕기 위해 다음 C++ 구현을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int odd = 0;
        int even = 0;
        for(int i = 0; i < chips.size(); i++){
            if(chips[i] & 1) odd++;
            else even++;
        }
        return min(odd, even);
    }
};
main(){
    Solution ob;
    vector<int> v1 = {2,2,2,3,3};
    cout << ob.minCostToMoveChips(v1);
}

입력

[2,2,2,3,3]