백준 2089 : -2진수

★★★☆☆

기본 식을 도출하는 데에 시간이 오래 걸렸다.
코드를 작성하는 것은 2진수 법에 근거해서 짜다보니 오래걸리지 않았다.

<나의 풀이>

#include <iostream>
#include <stack>
using namespace std;

int main() {
	long long n;
	stack<int> arr;

	cin >> n;

	if (n == 0) {
		cout << 0 << "\n";
		return 0;
	}
	while (n != 1) {
		if (n % (-2) ==-1) { //나머지가 음수
			n = (n / (-2)) + 1;
			//cout << "n :: " << n << "\n";
			arr.push(1);
		}
		else {
			arr.push(n%(-2));
			n = (n / (-2));
			//cout << "n :: " << n << "\n";
		}
	}
	arr.push(1);

	while (!arr.empty()) {
		cout << arr.top();
		arr.pop();
	}
	cout << "\n";
	
	return 0;
}

2진수의 경우, 10진수 값을 2로 계속 나누고, 그 나머지 값을 역순으로 출력하면 되었다.
-2진수의 경우, 2진수와 동일한 방식으로 진행할 때 나머지가 -1이 되는 경우가 문제가 되었다.
따라서 나머지가 -1인 경우에는 몫에 1을 더하여 나머지를 1로 만들어준다.

10진수 값이 1이 될때까지 진행하고, 마지막 1은 직접 array에 넣어주었다. (10진수 값이 1인 경우에는 while구문 자체가 돌아가지 않으므로.)