[2019 홍익대학교 프로그래밍 경진대회] 17830번 이진수씨의 하루 일과

문제

이진수 씨는 이진수를 사랑한다. 그의 하루 일과는 하루 종일 이진수 두 개를 생각해놓고, 그 두 수의 곱을 "오늘의 이진수"로 선정한다. 그리고 예쁜 종이를 한 장 사와 "오늘의 이진수"를 적은 후 액자에 전시한다. 그러나 그런 진수씨에게도 시련이 찾아왔으니, 종이를 사기 위해 나온 도중에 "오늘의 이진수"를 잊어버리고 만 것이다. 하지만, 진수 씨가 오늘 하루 생각해 놓은 두 이진수에 대해서는 어렴풋이 기억하고 있다.

  

그 두 이진수를 A와 B라고 하자. 진수 씨가 기억하는 사실은 다음과 같다. A와 B는 N개의 비트로 이루어져 있다. A의 모든 비트는 1이다. 하지만 B의 일부 비트는 기억하지 못한다. 여기서 "오늘의 이진수"를 어느 정도 추측해 볼 수 있다.

예를 들어, N = 4라면 A = 1111이다. 여기서 B = ?00?라고 해보자. ?는 기억하지 못하는 비트를 의미한다. 그렇다면 B는 0000, 0001, 1000, 1001중 하나일 것이다. 따라서 이 경우 "오늘의 이진수"는 A×B, 즉 0, 1111, 1111000, 10000111중 하나일 것이다. B는 leading zero를 포함할 수 있지만, "오늘의 이진수"는 leading zero를 생략한다. 즉, B는 맨 앞 자리가 1이 아닐 수 있지만, 진수씨가 "오늘의 이진수"를 적을 때에는 A×B=0일 때를 제외하면 맨 앞자리가 반드시 1이 되도록 0을 생략한다.

진수 씨는 "오늘의 이진수"에 비해 너무 크거나 작은 종이를 사고 싶지 않다. 따라서 "오늘의 이진수"를 쓸 때, 가능한 최대 자릿수와 최소 자릿수를 구해보고자 한다. 하지만, 진수 씨는 그의 일생 동안의 경험으로 큰 이진수를 빠르게 곱하는 것은 매우 어렵다는 것을 알고 있다. 따라서 여러분이 그 답을 대신 구해주자.

입력

첫 번째 줄에 테스트케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 

두 번째 줄부터 T개의 줄에 걸쳐, A와 B의 길이 N(1 ≤ N ≤ 1,000,000)과 B가 공백으로 구분되어 주어진다. B는 0, 1, ?로 이루어져 있으며, ?는 해당 비트를 기억하지 못함을 의미한다.

출력

T개의 줄에 걸쳐, 각 테스트케이스에 대해 "오늘의 이진수"의 최대 자릿수와 최소 자릿수를 공백으로 구분하여 출력한다.

 

A자리수 N과 B자리수 M일때 이진수 A*B의 자리수는 최대 N+M 최소 N+M-1이다.

곱의 길이 최대는 ?가 모두 1일때 최소는 0일때이므로 각각 만들어준다.

그때의 B의 길이를 각각 기억해두고

N+M인 경우는 첫 자리의 1 제외하고 그 후에도 1이 나온경우, N+M-1 은 첫자리만 1인 경우인데

예외 케이스는 두가지존재한다.

B가 1일때는 N+M도 N+M-1도 아니고 그냥 A그자체 즉 N이다.

또한 0일때는 곱한 뒤에 무조건 '0'이라는 길이 1이다.

 

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
string B;


int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		int N;
		cin >> N;
		cin >> B;
		string max_B = "";
		bool head = false;
		for (int i = 0; i < B.size(); i++)
		{
			if (!head)
			{
				if (B[i] == '1')
				{
					head = true;
					max_B += B[i];
				}
				else if (B[i] == '?')
				{
					head = true;
					max_B += '1';
				}
			}
			else
			{
				if (B[i] == '?')
				{
					max_B += '1';
					continue;
				}
				max_B += B[i];
			}
		}


		string min_B = "";
		head = false;
		for (int i = 0; i < B.size(); i++)
		{
			if (!head)
			{
				if (B[i] == '1')
				{
					head = true;
					min_B += B[i];
				}
				
			}
			else
			{
				if (B[i] == '?')
				{
					min_B += '0';
					continue;
				}
				min_B += B[i];
			}
		}
		if (min_B == "")
			min_B = "0";
		if (max_B == "")
			max_B = "0";


		if (max_B == "0")
		{
			cout << 1 << " ";
		}
		else if(max_B == "1")
		{
			cout << N << " ";
		}
		else
		{
			bool max_head = false;
			for (int i = 0; i < max_B.size(); i++)
			{
				if (max_B[i] == '1' && i != 0)
				{
					max_head = true;
					break;
				}
			}
			if (max_head)
				cout << N + max_B.length() << " ";
			else
				cout << N + max_B.length() - 1 << " ";
		}

		if (min_B == "1")
		{
			cout << N << endl;
		}
		else if (min_B == "0")
		{
			cout << 1 << endl;
		}
		else
		{
			bool min_head = false;
			for (int i = 0; i < min_B.size(); i++)
			{
				if (min_B[i] == '1' && i != 0)
				{
					min_head = true;
					break;
				}
			}
			if (min_head)
				cout << N + min_B.length();
			else
				cout << N + min_B.length() - 1;
			cout << endl;
		}

		

	}
}