BOJ 2089번 -2진수

BOJ : https://www.acmicpc.net/problem/2089

GitHub : https://github.com/junho0956/Algorithm/blob/master/2089/2089/%EC%86%8C%EC%8A%A4.cpp

 

-2진수에 대한 변환법은 2진수 변환법과 똑같다

다른 부분은 나눗셈을 할 때 몫과 나머지를 잘 건드려줘야되는 것

13을 2로 나누면 몫은 6, 나머지는 1이다.

하지만 -13 을 2로 나누면 몫을 -6, 나머지는 -1이 되는데

이 문제를 풀기 위해서는 -13 -> -7, 1 을 만들어야하는 과정을 이해해야한다.

 

다른분들 블로그를 읽어봤는데 개념을 제대로 파악하지 않고 외우기식 문제풀이만 하는 분들이 많았다.

그렇게하면 문제를 안푼거랑 똑같지않나 라는 생각이 든다.

 

2진수라는 것은 1과 0으로만 표현할 수 있다. -1은 표현이 안되는 수이다

이 개념을 이용해보자면 ==> -1을 1로 만들수 없을까? 가 되고

-1을 1로 만들려면 몫을 -1 만큼 더 주는 대신 나머지는 2를 더해주는 것이다.

===> -13 을 2로 나누면 몫은 -7, 나머지는 1 이 된다.

이 방법을 이용하면 나머지가 1,0으로만 떨어지면서 2진수로 표현이 가능해진다.

 

#include <cstdio>
#include <stack>
using namespace std;
#pragma warning(disable:4996)
stack<int> s;
int main() {
    int N;
    scanf("%d", &N);
    if (!N) s.push(0);
    while (N) {
        if (N > 0) {
            s.push(N % 2);
            N = N / 2 * -1;
        }
        else {
            if ((N * -1) % 2 == 0) {
                s.push(0);
                N = N * -1 / 2;
            }
            else {
                s.push(1);
                N = ((N * -1) + 1) / 2;
            }
        }
    }
    while (!s.empty()) printf("%d", s.top()), s.pop();
 
    return 0;
}