취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13230번 문제인 Bits equalizer이다.
문제는 아래 링크를 확인하자.

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

주어진 두 문자열 S와 T에 대하여, S와 T의 대응되는 위치에 있는 각 문자쌍 \((S_i,T_i)\)의 개수를 종류별로 세어 문제를 해결해보자.

먼저, \(S_i=T_i\)이면 이 위치는 전혀 건드릴 필요가 없다는 것은 쉽게 알 수 있다.

남은 쌍의 종류들 중 \((0,1)\)과 \((1,0)\)로 나타나는 위치의 문자들의 쌍들을 먼저 서로 가능한 위치를 바꾸고, 남은 문자들을 적절히 '?'를 채워 위치를 다시 바꾸는 전략으로 최소 횟수로 S를 T로 바꿀 수 있다. 이 때, ?를 어떻게 채워도 S의 0의 개수가 T보다 적다면 -1을, 그렇지 않다면 이와 같이 움직일 때의 그 횟수를 출력해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int T;
int slen;
string s1, s2;

void solve() {
	cin >> s1 >> s2;
	slen = s1.length();
	
	int cnt01 = 0, cnt10 = 0, cntq0 = 0, cntq1 = 0;

	for (int i = 0; i < slen; i++) {
		if (s1[i] == '0' && s2[i] == '1') cnt01++;
		else if (s1[i] == '1' && s2[i] == '0') cnt10++;
		else if (s1[i] == '?' && s2[i] == '0') cntq0++;
		else if (s1[i] == '?' && s2[i] == '1') cntq1++;
	}

	int mn = min(cnt01, cnt10);
	cnt01 -= mn, cnt10 -= mn;
	
	if (cnt01) cout << mn + cnt01 + cntq0 + cntq1 << '\n';
	else {
		if (cntq1 >= cnt10) cout << mn + cnt10 + cntq0 + cntq1 << '\n';
		else cout << -1 << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case " << t << ": ";
		solve();
	}
}