2089번: -2진수

문제:

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 2, 2, 2, 2이 표현 되지만 -2진법에서는 (-2) = 1, (-2) = -2, (-2) = 4, (-2) = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

입력:

첫 줄에 10진법으로 표현된 수 N이 주어진다.

풀이:

• 이 문제를 풀기 위해서는 우선 10진법을 2진법으로 바꾸는 간단한 방법을 알고 있어야 된다. 10진법을 2진수로 바꾸는 방법은 2로 나누어 나머지를 기록한다. 그러고 또 2를 나누어 나머지를 기록한다. 그렇게하여 기록 된 나머지를 제일 마지막에 한 연산부터 위로 적으면 그것이 2진법으로 나타낸 수 이다. 아래 그림을 보면 쉽게 이해할 수 있다.

출처: https://ourcalc.com/2진수-변환기/

• -2진법은 조금 특이한데 우선 나머지를 -2를 통해 구하면 나머지가 -1 혹은 0이 나온다. 예를들어 9같은 경우 -2로 나누면 -4고 나머지가 -1인 식으로 연산이 되기 때문이다. 따라서 입력값%-2 연산을 한 경우에 0이 아닌 경우에는 스택에 1을 넣어주면 된다. 어짜피 홀수면 -1 혹은 1일 것이기 때문이다.
• 이제 수를 -2로 나눌 때 숫자가 0보다 큰 경우와 0보다 작은 경우에 연산하는 방식이 다르다. 또한 마이너스인 경우에 짝수냐 홀수냐에 따라서도 연산이 바뀐다.
  • 입력값이 양수인 경우: 입력값이 양수인 경우에는 -2로 나누었을 때 짝수면 딱 맞아 떨어지지만 홀수면 소숫값자리가 남는데 이때 나온 값을 반올림을 해주어야 된다. c++는 int 값일 때 소숫자리를 알아서 제거하므로 음수인 경우에는 반올림하는 효과가 생긴다. 반올림을 해주어야 되는 이유는 예를 들어 설명하면 9 같은 경우 나머지를 +1인 상태로 표현할려면 9 = -2 * -4 + 1인 식이 나와야 된다. 따라서 -2에 곱해지는 숫자가 -4이여야 되기 때문에 -4.5를 반내림을 하여 -5가 되면 안된다.
  • 입력값이 음수인 경우: 입력값이 음수인 경우에는 두가지로 나뉜다. 짝수인 경우와 홀수인 경우다. 두 경우로 나뉘는 이유는 짝수인 경우에는 정확히 나누어 떨어져 연산을 그대로 하면 되는 반면 홀수인 경우는 음수를 -2로 나누게 되면 플러스 값이 되는데 이때 c++의 특성으로 뒷자리가 없어지면서 자연스럽게 반내림이 된다. 하지만, 우리가 해주어야 되는 것은 반올림이다. 예를 들면 -3인 경우 나머지가 1이 되도록 표현하면 -3 = -2 * 2 +1이 되어야 한다. 하지만 c++에서 -3을 -2로 나누면 2가 나오는 것이 아닌 1이 나온다. -3/-2=1.5이므로 0.5를 제거한 값이 나온것이다. 따라서 홀수인 경우에는 1을 더해주어야 된다.

코드:

#include <iostream>
#include <stack>

using namespace std;

int main(){
	int n;
	stack<int> binary;
	//입력
	cin >> n;
	//0인 경우 예외 처리
	if(n==0){
		cout<<0;
		return 0;
	}
	//이진법으로 변환 연산
	while(n){
		//나머지가 1인 경우(홀수인 경우)
		if(n%-2) binary.push(1);
		//나머지가 0인 경우(짝수인 경우)
		else binary.push(0);
		//n이 양수여서 그대로 나누어 주면 되는 경우
		if(n>0) n/=-2;
		//n이 음수여서 짝수와 홀수로 나뉘는 경우
		else if(n<0){
			//음수인데 짝수인 경우 나누어 떨어지므로 그대로 나누기
			if(n%2==0) n=n/-2;
			//음수인데 홀수인 경우에는 -2로 나뉠 시 반내림이 되기 때문에 1을 더하여 반올림
			else n=n/-2+1;
		} 
	}
	//출력
	while(!binary.empty()){
		cout<<binary.top();
		binary.pop();
	}
}