문제

-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진법 수를 출력한다.

예제

• 입력 : -13
• 출력 : 110111

풀이

오답

나는 처음에 -2로 몫이 1이 될때까지 나눠주면 되는 줄 알았다. 그중에 나머지가 -1인 경우는 1로 치환해주는 식으로. 예를 들면,

n = 8일 때,
1) 8 / -2 = -4, 0
2) -4 / -2 = 2, 0
3) 2 / -2 = -1, 0
4) -1 / -2 = 1(반올림), 1
--> 결과물 11000

근데 이게 되서 되는줄 알았는데 -13을 가지고 해보니까 답이 틀리게 나왔다.
그래서 구글링해본 결과 내가 바보같이 느껴졌다.

-13을 가지고 풀이를 해보면
1) -13 = -2 * 7 + 1
2) 7 = -2 * -3 + 1
3) -3 = -2 * 2 + 1
4) 2 = -2 * -1 + 0
5) -1 = -2 * 1 + 1
-> 110111

위처럼 계산을 해야했다....
계산식을 세워 코딩을 해보자

코드

초안

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n, tmp;
	vector <int> v;

	scanf("%d", &n);
	while (1)
	{
		if (n % -2 == 1 || n % -2 == -1)
			tmp = 1;
		else
			tmp = 0;
		v.push_back(tmp);
		if (tmp == 0 || n >= 0)
			n /= -2;
		else
			n = n / -2 + 1;
		if (n == 1)
        {
			v.push_back(1);
            break;
		}
	}
	vector <int> ::reverse_iterator riter;
	for (riter = v.rbegin(); riter != v.rend(); riter++)
		cout << *riter;
	return (0);
}

결과물은 잘 출력이 되나 이상하게 채점하면 메모리 초과가 뜨는...
그래서 vector 변수가 메모리를 많이 잡는다는 글을 봐서 재귀를 이용해서 시도해봤다.

#include <iostream>
#include <vector>
using namespace std;

void ft_base(long long n)
{
	long long tmp, cpy_n;

	tmp = n % -2;
	if (tmp == 0 || n > 0)
		cpy_n = n / -2;
	else
		cpy_n = n / -2 + 1;
	if (n == -1)
	{
		printf("11");
		return;
	}
	if (n != 1)
		ft_base(cpy_n);
	if (tmp == -1)
		tmp *= -1;
	printf("%lld", tmp);
	return ;
}

int main()
{
	long long n;
	
	scanf("%lld", &n);
	ft_base(n);
	return (0);
}

여기서 n = -1일때는 11을 출력해야해서 조건문으로 따로 넣어줬다.
근데 이부분도 메모리 초과...

메모리 초과에 대해서 공부해봐야 겠다.

정답

문제 해결했다. 입력값이 0일때가 문제였다. 0에대한 예외처리가 없어 오류가 뜨는 거였다.
그래서 n == 0일때 printf("0\n");을 해주고 마무리했다.

#include <iostream>
#include <vector>
using namespace std;

void ft_base(long long n)
{
	long long tmp, cpy_n;

	tmp = n % -2;
	if (tmp == 0 || n > 0)
		cpy_n = n / -2;
	else
		cpy_n = n / -2 + 1;
	if (n == -1)
	{
		printf("11");
		return;
	}
	if (n != 1)
		ft_base(cpy_n);
	if (tmp == -1)
		tmp *= -1;
	printf("%lld", tmp);
	return ;
}

int main()
{
	long long n;
	
	scanf("%lld", &n);

	if (n == 0)
		printf("0\n");
	else
		ft_base(n);
	return (0);
}

벡터 변수를 사용한것도 다시 짜서 해봤는데... 역시 메모리 초과가 떴다

최적화

일단 c++ 환경에서 몫과 나머지가 어떻게 출력되는지 확인해봤다.

13 = -6 * -2 + 1;
-13 = 6 * -2 - 1;
로 계산식이 성립 된다.
그럼 음수를 나눠줄 때 수에 -1 을 해줘서 계산을 해주면 더 간단하게 코딩이 가능하다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n, tmp;
	vector <int> res;

	scanf("%d", &n);
	if (n == 0 || n == 1)
	{
		cout << n << '\n';
		return (0);
	}
	while (n != 1)
	{
		if (n % -2 == 0)
			tmp = 0;
		else
			tmp = 1;
		if (n < 0)
			n = (n - 1) / -2;
		else
			n /= -2;
		res.push_back(tmp);
	}
	res.push_back(n);
	vector <int> ::reverse_iterator riter;
	for (riter = res.rbegin(); riter != res.rend(); riter++)
		cout << *riter;
	return (0);
}