글 읽기 - [힌트] 문제 접근 방법과 아이디어 입니다

helios789789 3년 전 0

S, T 의 같은 자리의 문자열을 {S, T} 처럼 표현하겠습니다.

이때 {1, 0} 의 경우 문제의 조건에서 혼자 바꿀 순 없고, 0과 1을 다른 자리와 교환하는 방식으로밖에 매칭이 안됩니다.

따라서 여기에서, {1, 0} 은 {0, 1} 이나 {?, 1} 과 0,1 을 바꾸는 방법으로 매칭시킬 수 있습니다.

이때 {0, 1} 은 1회의 교환으로, {?, 1} 은 2회의 교환으로 (? -> 1 로 바꿔줘야함) 매칭이 가능한데,

이때 귀류법으로 그리디 알고리즘이 적용 가능함을 증명할 수 있습니다.

간단히 말씀드리면, {?, 1} 을 {0, 1} 대신 {1, 0} 과 매칭하는 경우에서 {?, 1} 대신 남은 {1, 0} 을 사용하면 매번 교환 횟수를 1회 씩 아낄 수 있죠!

따라서 {1, 0} 에 대해서 {0, 1} 과 매칭을 한 후, 아직 {1, 0} 남았다면 {?, 1} 과 마저 매칭을 해줍니다.

매칭이 불가능한 경우는 {1, 0} 의 개수 > {0, 1} 의 개수 + {?, 1} 의 개수 인 경우 이며 이때 아무리 잘 바꿔도 {1, 0} 이 남으므로 매칭이 불가능 합니다.

by injae, Kim

/*
https://www.acmicpc.net/problem/3806

완전탐색과 DP 는 조합의 경우의 수가 너무 많으므로, 그리디로 해결
S = {0, 1, ?}, T = {0, 1} 이므로 S X T = { {0, 0}, {0, 1}, {1, 0}, {1, 1}, {?, 0}, {?, 1}}

이떄, S X T 의 모든 조합에 대해서 {0, 0}, {1, 1} 는 변경할 필요 없음
{1, 0} 은 문제의 규칙에서 바꾸는 방법이 {*, 1} 과 교환하는 방법 밖에 없음
이때 {*, 1} = {?, 1} or {0, 1} 이며 {?, 1} 는 바꾸는데 2회, {0, 1} 은 1회 소모 됨
따라서, 바꾸는 횟수가 더 적은 {0, 1} 을 {1, 0} 과 최대한 매칭시킨 후 남은 {1, 0} 과 {?, 1} 을 매칭

{1, 0} 의 개수 > {0, 1} 의 개수 + {?, 1} 의 개수 인 경우 아무리 잘 바꿔도 {1, 0} 이 남으므로 불가능
*/

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <string.h>
#pragma warning(disable:4996)
using namespace std;

const int INF = 987654321;
int N, M, K;



void solve() {


}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int ret = 0;
		int one2zero = 0;   // {1, 0}
		int zero2one = 0;   // {0, 1}
		int something2one = 0;  // {?, 1}
		int something2zero = 0; // {?, 0}

		string s, t;
		cin >> s;
		cin >> t;

		for (int j = 0; j < s.length(); j++) {
			if (s[j] != t[j]){
				if (s[j] == '1' && t[j] == '0')
					one2zero++;
				else if (s[j] == '0' && t[j] == '1')
					zero2one++;
				else if (s[j] == '?' && t[j] == '1')
					something2one++;
				else if (s[j] == '?' && t[j] == '0')
					something2zero++;
			}
		}

		if (one2zero > zero2one + something2one) {
			cout <<"Case "<<i+1<<": " << -1 << endl;
			continue;
		}

		int zero_one_swap = min(one2zero, zero2one);
		ret += zero_one_swap;
		one2zero -= zero_one_swap;
		zero2one -= zero_one_swap;

		if (one2zero > 0) {

			int something_one_swap = min(one2zero, something2one);
			ret += something_one_swap * 2;
			something2one -= something_one_swap;

			ret += something2one;
			ret += something2zero;
		}
		else {
			ret += something2one;
			ret += something2zero;
			ret += zero2one;
		}

		cout << "Case " << i + 1 << ": " << ret << endl;
	}



	solve();

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.