2729 이진수 덧셈

백준 추천 오늘의 문제에 나온

첫번째 문제 이진수 덧셈

https://www.acmicpc.net/problem/2729

브론즈 1따리 길래 후딱 풀고 다른 문제 풀려다가 한시간 날아감

1. 문제

---

간단 설명

이진수의 덧셈을 구현한다

그러나 길이가 최대 80자리인 수가 주어짐. 합은 최대 81자리수까지

2. 문제 분석

---

필요변수

정수형 중에서 가장 긴 unsigned long long int도 약 20자리까지밖에 처리하지 못한다

그러므로 문자열로 처리해야함

string a, b

덧셈에 필요한 자리 올림 int carry, 자리수의 합 int sum 등 필요

주의점

• 길이는 최대 80자리

알고리즘

bitset 사용해보려다가 실패

bitset에는 더하기 연산자가 없음!

문자열을 이용해 직접 carry를 이용한 덧셈 연산 구현

c++ 에서는

1. 케이스 수 T 입력받기
2. 다음부터 T번 반복
3. 숫자 a, b를 문자열로 입력받음
4. 자리수가 긴 숫자를 a로 둠
5. a, b를 계산하기 쉽게 역순으로 뒤집음
6. 0~b 자리수 까지 덧셈을 수행. carry를 이용해 자리 올림. result에 sum을 추가함
7. 나머지 b+1 부터 a까지 덧셈을 수행. result에 sum을 추가해줌
8. carry가 남아있다면 result 문자열의 마지막에 '1' 덧붙여줌
9. result 문자열 뒤집기

파이썬에서는

1. n번 입력받기
2. a, b입력받기
3. a와 b를 이진수로 변환
4. a와 b를 더한 뒤, 0b를 제거하여 출력

언어별로 난이도가 다른 문제가 있는데, 이번 문제는 그게 더 심했던것 같다

C++에선 빡구현이였다면

파이썬에는 bin 라이브러리 사용법을 알고있었으면 1분컷 문제였다

억울해서 파이썬도 공부할 예정

3. 소스코드

---

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 문자열 a, b를 더해 결과를 문자열로 리턴하는 함수
string BinSum(string a, string b) {
	string result;

	if (a.size() < b.size()) {
		swap(a, b);
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	int carry = 0;

	// b가 더 작으므로
	for (int i = 0; i < b.size(); i++) {
		int sum = (a[i] - '0') + (b[i] - '0') + carry;
		if (sum > 1) carry = 1;
		else carry = 0;
		result.push_back((sum % 2) + '0');
	}

	// a의 나머지 더해주기
	for (int i = b.size(); i < a.size(); i++) {
		int sum = (a[i] - '0') + carry;
		if (sum > 1) carry = 1;
		else carry = 0;
		result.push_back((sum % 2) + '0');
	}
	
	if (carry) result.push_back('1');

	reverse(result.begin(), result.end());

	if (result.find_first_of('1') != string::npos) {
		result = result.substr(result.find_first_of('1'));
	}
	else {
		result = "0";
	}

	return result;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int T; cin >> T;
	while (T--) {
		string a, b;
		cin >> a >> b;

		cout << BinSum(a, b) << endl;
	}

	return 0;
}

 n = int(input())
   for _ in range(n):
       a, b = input().split(" ")
       a = int(a, 2)
       b = int(b, 2)
       print(bin(a+b).replace("0b",""))