[C/C++] 백준 - 12782번 : 비트 우정지수

https://www.acmicpc.net/problem/12782

12782번: 비트 우정지수

---

각 다른 비트를 최소한의 연산으로 같게 만드는 문제이다.

같은 자리에 비트가 같으면 고려하지 않고 다를 경우만 고려한다.

문자열 s1, s2의 각 자리 비트가 다를 때 그 형태가 0-1로 다른 경우와 1-0으로 다른 경우만 존재한다.

이러한 경우를 각각 모두 세어준다.

 

그럼 결국 최소한의 개수로 변환하기 위해서는 0-1과 1-0의 교환을 최대한 많이 해야하여 0->1, 1->0의 경우를 최소한으로 해야하는 것이다. 따라서 수학적으로 이를 나타내어주기만 하면 된다.

 

0-1로 다른 형태의 개수를 세어준다 : zeroToOne

1-0로 다른 형태의 개수를 세어준다 : oneToZero

 

그리고 자리 바꿔주는 경우 최대 경우의 수는 위에 두 가지 경우 중 더 작은 수만큼 가능하다는 뜻이므로, 

min + (max - min)이 정답이 된다.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF LLONG_MAX-1
#define Mod 1234567
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;

int solution(string& s1, string& s2) {
	int oneToZero = 0;
	int zeroToOne = 0;
	for (int i = 0; i < s1.size(); i++) {
		if (s1[i] == s2[i]) continue;
		if (s1[i] == '1') oneToZero++;
		else zeroToOne++;
	}

	if (oneToZero < zeroToOne) {
		return oneToZero + (zeroToOne - oneToZero);
	}
	else if (oneToZero > zeroToOne) {
		return zeroToOne + (oneToZero - zeroToOne);
	}
	else {
		return oneToZero;
	}
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s1, s2;
		cin >> s1 >> s2;
		cout << solution(s1, s2) << endl;
	}
}

int main() {
	fastio;
	input();
	
	return 0;
}