백준 BOJ 2089 - -2진수

USACO(4)

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

2089번: -2진수

진수 변환 방법에 대해서 먼저 숙지해야 하는 문제.

10진수 >> 2진수 변환을 계산할수 없으신 분들이라면

이 문제를 잡기 전에 2진수 변환 먼저 배우고 오는 것이 좋다고 생각한다.

 

일반적인 2진수 변환은

2로 나눈 나머지를 저장하고

숫자를 2씩 나눠간 다음

저장한 값들을 뒤집어서 출력해준다.

 

-2진수 변환도 크게 다를것이 없다.

-2로 나눈 나머지를 저장하고,

숫자를 -2로 나눠가면서 계산한 다음

저장한 값들을 뒤집어서 출력해준다.

 

-2진수 변환이 2진수 변환과 다른 것은,

-2로 나눈 나머지가 -1이 될수 있다는 것이다.

 

나머지를 0과 1 단 두가지만 남겨주어야

이 나머지를 저장한 다음 뒤집어서 출력해줄 수 있기 때문에,

 

예시로 제공된 -13의 경우

(-2 * 6) + (-1) 이 아닌 (-2 * 7) + (1) 으로 변환해주는 과정이 필요하다.

즉, 나머지가 -1인 경우 몫을 1 올려주고, 나머지를 2 올려주는 연산을 추가적으로 진행해주면

 

-13 = (-2*7) + 1

7    = (-2*-3) + 1

-3   = (-2*2) + 1

2    = (-2*-1) + 0

-1   = (-2*1) + 1

1    = (-2*0) + 1

으로,

저장되는 순서는 111011, 뒤집어 출력하면 110111으로 정답을 구할 수 있게 된다.

 

이렇게 0이 될때까지 나눠가는 방법을 택하면,

입력으로 0이 주어지는 경우에

아무런 연산을 하지 않기 때문에

이부분을 따로 처리해주면 문제를 해결할 수 있다.

 

소스코드 펼쳐보기

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

// -13 -> -2*7 + 1
// 7   -> -2*-3 + 1
// -3  -> -2*2 + 1
// 2   -> -2*-1 + 0
// -1  -> -2*1 + 1
// 1   -> -2*0 + 1

stack<int> s;

int main(){
	int N;
	cin >> N;
	
	do{
		int tmp = N%-2;
		N /= -2;
		
		if(tmp<0){
			N++;
			tmp = 1;
		}
		s.push(tmp);
	}while(N);
	
	while(!s.empty()){
		cout << s.top();
		s.pop();
	}
	return 0;
}