[백준][C++] 5893: 17배

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

 

최대 1000자리 수가 들어올 수 있기 때문에 정수형으로 변환하면 안되고 string이나 bitset 등을 사용해야 합니다

17배 = 16배 + 1배 이런식으로 계산하면 쉽습니다. a=(a<<4) + a 이렇게 하면 되는데 더하기는 직접 구현해야 합니다. 논리회로 시간에 했던 Full adder 기억하시죠?

물론 파이썬이면 이렇게 안해도 간단하게 풀 수 있을겁니다 (아마도)

#include <bits/stdc++.h>
using namespace std;


constexpr size_t sz = 1005;

bitset<sz> add(const bitset<sz>& a, const bitset<sz>& b) {
	bitset<sz> ret;

	bool carry = false;
	for (auto i = 0; i < sz; ++i) {
		bool sum = a.test(i) ^ b.test(i) ^ carry;
		carry = (a.test(i) & b.test(i)) | (carry & (a.test(i) ^ b.test(i)));

		ret.set(i, sum);
	}

	return ret;
}

void print(const bitset<sz>& a) {
	bool flag = false;
	for (int i = sz - 1; i >= 0; --i) {
		if (!flag && a.test(i))
			flag = true;

		if (flag)
			cout << a.test(i);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	bitset<sz> a, b;
	cin >> a;

	b = a;
	a <<= 4;

	print(add(a, b));

	return 0;
}

출력할 때 leading zero들은 안나오게 해줘야 합니다.