출처 BOJ

-2진수

문제

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 $2^{0}, 2^{1}, 2^{2}, 2^{3}$이 표현 되지만 -2진법에서는 $(-2)^0 = 1, (-2)^1 = -2, (-2)^2 = 4, (-2)^3 = -8$을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 10진법으로 표현된 수 N(-2,000,000,000≤N≤2,000,000,000)이 주어진다.

출력

-2진법 수를 출력한다.

예제

범위체크

-20억$\ge \ge$20억 $/ge INT$
곱하기,덧셈연산이 아닌 나눗셈 연산을 하기 때문에

풀이

10진수를 -2진수로 인수분해하면 됨(10진수→2진수변환과 유사)
주의할것! 음수나눗셈
9 / -2 = -2 * -4 + -1 → 9 / -2 = -2 * -5 + 1
나머지가 -1이 아니라 1이 되도록 변경해야함

코드

방법 code

#include<cstdio>
#include<stack>
#define DIV -2

using namespace std;

int main(){
	int num;
	scanf("%d",&num);
	stack<int> S;

	do{
		int left = num % DIV;
		num = num/DIV;
		
		if(left<0){
			left = 1;
			num++;
		}
		S.push(left);
	}while(num != 0);

	while(!S.empty()){
		printf("%d",S.top());
		S.pop();
	}
	printf("\n");
}

복잡도