[C++/백준 1212번] -2진수

 

 

대략 황당했던 문제. 처음에 보고 이걸 어떻게 풀어야 하나 생각했다.

 

진법에 맞게 -2 로 나누되, 컴파일러의 양수 / 음수 , 음수 / 양수 나눗셈에 대한 이해를 요하는 문제였다. 

 

C/ C++ 컴파일러에서는  13 / -2  가 -6 이 나오고, 파이썬에서는 13 / -2 가 -7 이 나온다고 알려져 있다. 이는 컴파일러의 계산 차이에서 오는 것인데, 우리가 -2로 나눌 때 나머지가 음수가 나오면 진법에 적용을 할 수 없으므로 13 / -2 는 (-2) * ( -6)  + 1 으로 나타내야 한다.

 

예시인 -13 을 예시로 들어보자.

 

-13 / -2 -> (-2) * 7  + 1

7 / -2   ->  (-2) * (-3) + 1

-3  / -2 -> (-2) * (2) + 1

2  /-2 ->  (-2) * (-1) + 0 

-1 / -2 -> (-2) * (1) + 1

1 

 

110111 로 정답이 잘 나온다. 따라서 저장 해 줄 때 나머지가 1 이 나오는 경우는 n-1 을 -2로 나눈 것을 저장해 주면 된다.

 

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

int main() {


    int N;

    cin >> N;

    int cnt = 0;

    if(N == 0)
    {
        cout << "0";
        return 0;
    }

    string result = "";
    while(N)
    {
        if(N % -2 == 0)
        {
            result = "0" + result;
            N = N / -2;
        }
        else
        {
            result = "1" + result;
            N = (N-1) / -2;
        }

    }

    cout << result << endl;





    return 0;
}