[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이다.

 

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

GitHub - sbl133/BOJ

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