[BOJ 2089 // C++] -2진수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2089번 문제인 -2진수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2089

2089번: -2진수

이 문제에서 말하는 -2진수는 negabinary number으로 검색하면 많은 자료를 구할 수 있을 것이다.

일반적인 이진수와 다르게, negabinary number의 각 자리는 (-2)의 거듭제곱을 나타낸다.

negabinary number은 양의 정수와 음의 정수를 -와 같은 부호의 표기를 따로 하지 않고 0과 1로 같이 나타낼 수 있다는 점에서 생각해 볼 가치가 있다.

 

10진수를 negabinary number로 바꾸는 것은 어렵지 않은데, 일반적인 이진수를 찾듯이 하다가 음의 지수를 나타내는 자리에서는 그 자리에 해당하는 숫자를 한자리 더해주는 것을 반복하면 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <stack>
using std::cin; using std::cout;
using std::stack;

stack<int> negabinary;

int main()
{
    int N; cin >> N;
    bool sign = 0; // 0: positive, 1: negative
    while (N != 0) {
        if (N & 1) negabinary.push(1);
        else negabinary.push(0);
        if (sign) {
            N++;
            sign = false;
        }
        else sign = true;
        N >>= 1;
    }
    if (negabinary.empty()) cout << 0; // 0의 경우 빈 스택이므로 예외처리
    else {
        while (!negabinary.empty()) {
            cout << negabinary.top();
            negabinary.pop();
        }
    }
    return 0;
}