[백준 2089번] -2진수 (C++)

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

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

int N;

int main() 
{
    cin >> N;
    if(N==0)
    {
        cout << 0;
        return 0;
    }
    vector<int>v;
    while(N!=0)
    {
        if(N%-2==0)
        {
            N/=-2;
            v.push_back(0);
        }
        else
        {
            N = (N-1)/-2;
            v.push_back(1);
        }
    }
    reverse(v.begin(), v.end());
    for(auto i : v) cout << i;
    
    return 0;
}

 

일반 2진법이 2를 나누며 나머지를 통해 표현한 것 처럼, 마찬가지로 -2로 나누며 남은 나머지를 통해 표현가능하다.

다만 주의할점은 N의 값이 홀수 일때이다.

문제의 예시를 들어 -13의 경우, (-2)*(-7)+1 또는 (-2)*(-6)-1로 표현이 가능할 것이다.

양수 13의 경우는 (-2)*(-6)+1 또는 (-2)*(-7)-1로 표현이 가능할 것이다.

우리는 나머지가 양수 1이어야만 하므로, 후자가 아닌 전자를 선택해야 한다.

 

이를 처리하기 위해 홀수인 경우는 N의 값을 -1을 먼저 감소시키고, 이후에 -2로 나눠준다.

짝수인 경우는 그대로 -2를 나눠주면 되고, 각 나눠준 케이스에 따라 0 또는 1을 벡터에 넣어준다.

이렇게 넣은 값은 역순이기에 다시 뒤집어서 출력해주면 된다.