문제설명

문제

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 2⁰, 2¹, 2², 2³이 표현 되지만 -2진법에서는 (-2)⁰ = 1, (-2)¹ = -2, (-2)² = 4, (-2)³ = -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진법 수를 출력한다.

접근

2로 계속 나누며 나머지를 반대로 읽어 2진수를 구하는 방법과 큰 틀에서는 같다. 손으로 직접 2진수를 구하는 방법으로 -2진수를 해봤으면 쉽게 풀 수 있는 문제이다.

-2로 나누면서 나머지가 음수(-1)로 나올 때, 2를 더해 양수(+1)로 바꿔주고 몫에 1을 더해주면서 n 값이 0이 될 때까지 계속 나눠가며 나머지를 저장한다. 저장한 나머지를 뒤집어 출력하면 -2진수를 찾을 수 있다.

코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    long long n, r;
    string ans = "";
    cin >> n;

    while(n != 0){
    	r = n%-2;
    	n = n/-2;
    	
    	if(r < 0){
    		r+=2;
    		n+=1;
		}	
		ans += to_string(r);
	}
	
	if(ans.size() == 0)
		cout << 0 << endl;
	else{
		reverse(ans.begin(), ans.end());
		cout << ans << endl;
	}
}

참고

BOJ #2089

이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)