[백준 - 3806] S를 T로

#include <iostream>
using namespace std;

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

	string S, T;
	int result;
	int S_one;
	int S_question;
	int T_one;
	for (int k = 1; k <= N; ++k)
	{
		result = 0;
		S_one = 0; S_question = 0;
		T_one = 0;

		//각 일의 개수 구하기
		cin >> S >> T;
		for (int i = 0; i < S.length(); ++i)
		{
			if (S[i] == '1') ++S_one;
			else if (S[i] == '?') ++S_question;
			if (T[i] == '1') ++T_one;
		}

		//변환이 가능한지 확인
		if (T_one < S_one)
		{
			cout << "Case " << k << ": -1\n";
			continue;
		}

		//각 인덱스를 모두 탐색
		for (int i = 0; i < S.length(); ++i)
		{
			//S가 1일때 다른 경우
			if (S[i] == '1' && T[i] == '0')
			{
				//뒤의 0일때 다른 경우의 인덱스와 변경한다.
				for (int j = i; j < S.length(); ++j)
				{
					if (S[j] == '0' && T[j] == '1')
					{
						S[i] = '0'; S[j] = '1'; ++result;
						break;
					}
				}
				//뒤에 0이고 다른 경우가 없으면 T의 1과 맞물리는 물음표와 변경한다.
				if (S[i] == '1')
				{
					for (int j = 0; j < S.length(); ++j)
					{
						if (S[j] == '?' && T[j] == '1')
						{
							S[i] = '0'; S[j] = '1'; result += 2; --S_question;
							break;
						}
					}
				}
			}
			//S가 0일때 다른 경우
			else if (S[i] == '0' && T[i] == '1') 
			{
				//뒤의 1일때 다른 경우의 인덱스와 변경한다.
				for (int j = i; j < S.length(); ++j)
				{
					if (S[j] == '1' && T[j] == '0')
					{
						S[i] = '1'; S[j] = '0'; ++result;
						break;
					}
				}
				//못 찾을 경우
				if (S[i] == '0')
				{
					S[i] = '1'; ++result;
				}
			}
		}

		cout << "Case " << k << ": "<<result + S_question<<"\n";
	}
	return 0;
}

---

||사고 과정

규칙찾는게 어려웠던 문제다.

문자열 S는 0, 1, ? 로만 이루어져 있으니까 각 숫자에서 T와 다를때

어떻게 해야 중복 없이 최소값이 나올 수 있는지 고민했다.

 

문자열 S를 한번 싹 탐색하면서 확인한다고 생각했을 때

최대한 물음표가아닌 0, 1을 모두 T와 맞추려고 했다.

이유는 물음표는 어떠한것도 될 수 있기에 0,1만 잘 맞춰놓으면

남은 물음표의 개수만큼 결과에 더하면 되기 때문이다.

 

S가 1일때 다를 경우:

뒤의 S가 0일때 T와 다른 인덱스와 변경하는게 최고로 좋다고 생각했다.

이유는 뒤의 인덱스까지 맞춰지기 때문.

이러한 경우가 없다면 남은건 뒤의 S가 ?인 인덱스와 변경뿐이다.

 

S가 0일때 다를 경우: 

이것도 뒤의 S가 1일때 T와 다른 인덱스와 변경하는게 최고로 좋다고 생각했다.

단 이제 이러한 경우가 없을때는 물음표와 변경도 가능하고 0이 1로 변경도 가능하다.

이 둘은 어차피 연산 비용이 2로 같아서 물음표는 나중에 한번에 계산하기도 편하고 해서

0을 1로 바꾸는 계산을 하였다.

 

이렇게 0,1을 모두 맞추고 남은 물음표의 개수를 결과에 더해주었다.

---

||사용 기법

• Greedy???

---

||나아 진것

• 최선을 생각한것 좋았음

경우의 수 중에 어떤 것이 중복없는 최선의 연산인지 확인하는게 좋았다.