[BOJ] 백준 17830 이진수씨의 하루 일과 c++

BOJ 문제 링크: https://www.acmicpc.net/problem/17830

17830번: 이진수씨의 하루 일과

길이가 N인 이진수 A, B가 있다. A는 모든 자리의 수가 1로만 채워져 있고, B는 각 자리에 0, 1, ? 셋중 하나가 올 수 있다. 

B의 ?를 0 또는 1로 적절히 변환시켜서 A와 B를 곱했을때 자릿수가 최대가 되는 경우의 자릿수, 자릿수가 최소가 되는 경우의 자릿수를 구하는 문제이다.

 

A와 B의 곱이 최대자릿수를 가지려면 가장 큰 값이 되어야 하고, 그러려면 B의 ?는 모두 1로 변환시켜야 한다.

마찬가지로 A와 B의 곱이 최소자릿수를 가지려면 가장 작은 값이 되어야 하고, 그러려면 B의 ?는 모두 0으로 변환시켜야  한다.

곱의 자릿수가 몇인지는 값이 범위가 너무커서 직접적인 계산으로는 알기 어렵다.

계산할 수 있는 방법으로는 A가 모두 1이므로 B의 최고자리수 미만의 자리에 1인 자리가 있으면 N+B의 자리수,

B의 최고자리수 미만의 자리에 1인 자리가 없으면 N + B의 자리수 - 1 임을 몇개의 예를 통하면 금방 알아차릴 수 있다.

예를 들어 N이 10인 경우 1111111111*0010000001 와 1111111111*0011111111의 자리수는 10 + 8 = 18이다.

하지만 1111111111*0010000000의 자리수는 17이다.

 

	#include<iostream>
	using namespace std;
	// 최대 자릿수, 최소 자릿수
	int resultBig, resultSmall;
	// 이진수의 길이
	int n;
	void Mr_Binary(string str) {
	// 최대값의 가장 높은자리의 자릿수, 최솟값의 가장 높은자리의 자릿수
	int maxHigh = 0, minHigh = 0;
	// maxHigh, minHigh 이하의 자리에 1이 하나라도 있나?
	bool maxIsLow = false, minIsLow = false;
	// str값을 2^0자리부터 탐색
	for (int i = str.size()-1; i >= 0; i--) {
	// 1이 오면 최댓값 최솟값 모두 갱신
	if (str[i] == '1') {
	// 이전에 최고 자릿수가 있었으면 최고자리 미만의 자리에 1이 하나이상 존재
	if (maxHigh != 0) maxIsLow = true;
	if (minHigh != 0) minIsLow = true;
	// 최댓값, 최소값의 최고 자릿수 갱신
	maxHigh = minHigh = n - i;
	}
	// ?이 오면 최댓값만 갱신
	else if (str[i] == '?') {
	if (maxHigh != 0) maxIsLow = true;
	maxHigh = n - i;
	}
	}
	// 최댓값 처리
	if (maxHigh == 0)
	resultBig = 1;
	// 최고 자리 미만의 자리에 1이 존재하지 않으면 최고자리수+n에서 1을 뺌
	else
	resultBig = maxIsLow ? maxHigh + n : maxHigh + n - 1;
	// 최솟값 처리
	if (minHigh == 0)
	resultSmall = 1;
	else
	resultSmall = minIsLow ? minHigh + n : minHigh + n - 1;
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	string str;
	cin >> n;
	cin >> str;
	Mr_Binary(str);
	cout << resultBig << " " << resultSmall << endl;
	}
	}

view raw [BOJ] 백준 17830 이진수씨의 하루 일과.cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2317830.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!