문제

---

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -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진법 수를 출력한다.

• 제한
  -2,000,000,000 ≤ N ≤ 2,000,000,000

풀이

---

다른 N진수 계산과 마찬가지로 주어진 숫자를 -2 로 나누면서 몫을 구하면 된다.

단, -2진수이지만 2진수와 마찬가지로 표현되는 만큼 0 또는 1로 나머지가 나와야 한다.

그러나 음수와 양수의 계산 과정에서 나머지가 -1 이 나오는 경우가 발생하므로
이를 방지하기 위한 방법이 필요하다.

예를 들어 7을 -2진수로 표현하는 과정에서

7 / -2 = -3...1
-3 / -2 = 1...-1

위의 상황처럼 나머지가 -1로 나와 -2진수로 표현할 수가 없게 된다.

만약 N이 짝수일 경우는 나머지가 음수나 양수로 나누는 것에 상관없이
항상 나머지가 0으로 나오기 때문에 상관이 없다.

8 = -2 * 4

그러나 만약 홀수일 경우에는 표현할 수 있는 방법이 나머지가 1 이거나 -1 인 경우가 생긴다.

7 = -2 (-3) + 1 or 7 = -2 (-4) - 1
몫 -3 은 7 - 1 / -2

-3 = -2 (2) + 1 or -3 = -2 (1) - 1
몫 -2 는 -3 - 1 / -2

우리는 나머지가 1이 나오는 경우를 통해 -2진수를 표현해야 되므로
N 이 홀수인 경우 N - 1 / -2 를 통해 나머지가 +1 로 표현될 수 있도록 해야한다.

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;

    cin >> N;

    vector<int> my_v;

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

    while (N != 0)
    {
        if (N % -2 == 0)
        {
            my_v.push_back(0);
            N /= -2;
        }
        else
        {
            my_v.push_back(1);
            N = (N - 1) / -2;
        }
    }

    reverse(my_v.begin(), my_v.end());

    for (int i = 0; i < my_v.size(); i++)
        cout << my_v[i];

    return 0;
}

리뷰

사실 -2진수를 표현하는 방법을 이해하는데 생각보다 오래 걸렸다..
그냥 다른 N진수처럼 N 으로 계속 나누면서 나오는 나머지 값으로 표현되는 수라는 것을
떠올리는 데 조금 오래걸렸다...