[BOJ 5893, 약간 쉬움] 17배 (C++)

개인적인 난이도

약간 쉬움

난이도에 비해 구현이 어려운 문제임

 

입력의 크기가 C++의 long long 범위를 벗어나는 경우, C나 C++로는 구현이 어려워진다
vector나 string의 무한 길이의 자료형을 사용해 구현해야 한다.
(또는 bigint를 사용해 구현해야 한다고 하는데 안해봤다)

C++ 대신 입력의 크기 제한이 없는 파이썬으로 풀면 매우 쉽게 풀리는 문제이고, 그래서인지 난이도가 브론즈 4로 잡혀 있다
[BOJ 10757번: 큰수 A+B] 얘도 비슷하게 파이썬으로 풀면 코드 세줄로 끝나는데 C++로는 1000B정도 작성해야 풀린다

 

---

풀이)

숫자 25를 17배한다고 생각해 보자.
25*17 = 25*(16 + 1) = 25*16 + 25 와 동일하다.

25는 이진수로 11001이다
이걸 2배하면 110010이다
4배하면 1100100이다
16배 하면 110010000이다. 즉, 어떤 이진수를 16배 하기 위해선 그냥 맨뒤에 0 4개를 붙이면 된다.

그다음 110010000에 11001을 더하면 내가 원하는 25*17의 답이 나온다
이진수끼리의 덧셈이 어떻게 이루어지는지 생각하면서
그 부분을 조건문 덕지덕지 붙이면서 구현하면 풀린다

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;
int main(void) {
	fastio;
	string s;cin>>s;
	string s2 = s+"0000";
	s="0000"+s;
	string s3="";
	char carry = '0';
	for (int i = s.length()-1; i >= 0; i--)
	{
		if(s[i]=='1'&&s2[i]=='1'){
			if(carry=='0'){
				s3='0'+s3;
			}
			else{
				s3='1'+s3;
			}
			carry='1';
		}
		else if(s[i]=='0'&&s2[i]=='0'){
			s3=carry+s3;
			carry='0';
		}
		else{
			if(carry=='1'){
				s3='0'+s3;
				carry='1';
			}
			else{
				s3='1'+s3;
				carry='0';
			}
		}
	}
	if(carry=='1')s3='1'+s3;
	cout<<s3;
	return 0;
}

string을 이용해서 풀었다.

s를 입력받고, s를 16배한 s2를 만들고,
s와 s2의 덧셈을 구현하기 위해 s의 앞에 0 4개를 붙이고 (length를 같게 하기 위해)
carry를 저장할 변수를 만들어서, 이진수끼리 더하면서 발생하는 자리올림수를 저장했다.

마지막에 남아있는 carry를 고려하지 않아서 한번 틀렸다