알고리즘(C++) / 백준 2089 : -2진수

2089 : -2진수

http://boj.kr/2089

2089번: -2진수

 

문제

-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,000,000,000 ≤ N ≤ 2,000,000,000

 

출력

-2진법 수를 출력한다.

 

코드

//2089 -2진수
#include <iostream>
#include <stack>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	stack <int> binary;

	if (N == 0) {
		binary.push(0);
	}
	else {

		while (N != 0) {
			if (N % -2 == -1) {
				binary.push(1);
				N = N / -2 + 1;
			}
			else {
				binary.push(N % -2);
				N /= -2;
			}
		}
	}
	while (!binary.empty()) {
		cout << binary.top();
		binary.pop();
	}
	cout << "\n";

	return 0;
}

 

설명

-2로 나눈 나머지를 stack에 저장하여 first in last out으로 출력하면된다. 

이때 1과 0으로 출력되어야하는데 -2로 나눈 나머지가 -1이면 몫을 1 증가시켜 나머지를 1로 만들어준다.

예를 들어 -3을 -2로 나누면 몫이 1 나머지 -1이다. 몫을 1 증가시켜 2로 만들어주면 나머지가 1이 된다. 이렇게 1과 0으로 -2진법 수를 구할 수 있다. 

 

결과

 

고찰

N이 0일 때를 추가 해주지 않아서 틀렸다.

N이 0일 때도 값을 구할 수 있도록 해주어야한다.

 

난이도

●○○○○