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

 

이걸 내가 왜 못풀었지.ㅜㅜ 이걸 왜.... 그냥 2진수로 계산하고 홀수일때만 신경써서 계산하면 된다.

#include <bits/stdc++.h>
using namespace std;
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;

  string bi;

  if (n == 0) {
    bi = "0";
  }

  while (n != 0) {
    if (n%-2 == 0) {
      bi += "0";
      n/=(-2);
    } else {
      bi += "1";
      n = (n-stoi("1"))/-2;
    }
  }
  reverse(bi.begin(),bi.end());
  cout << bi;

}
 

문제의 예시가 -13을 -2진수로 바꾸는 건데. 이걸 그냥 13을 2로 하는 것을 보여주겠다. 물론 똑같이 하면 값이 다르지 않기 때문에 코드처럼 보정을 살짝해보자.

 

13 % 2 => 1

12 / 2 => 6

 

6% 2 = > 0

6 / 2  => 3

 

3 % 2 => 1

2 / 2 => 1

 

2 % 2 => 0

2/ 2  => 1;

 

1 % 2 => 1

0 / 2 => 0

종료

 

답은 : 10101이된다. 하지만 진짜 답은 110111이된다.ㅜㅜ 아마 이래서 틀린듯 싶다. 이제 -2를 적용한 상태에서  진행하면 답이 달라지겠지 아마도... 

-13 % -2 => 1

-14 / -2 => 7

 

7 % -2 => 1

6 / -2  => -3

 

-3 % -2 => 1

-4 / -2 => 2

 

2 % -2 => 0

2 / -2   => -1

 

-1 % -2 => 1

-2 / -2 => 1

 

1 % -2  => 1

0 / -2 => 0

 

값을 계산하면 110111이 된다. 이 문제 의 핵심은 음수이고, 그걸 다시 양수로 바꾸는 과정에서 약간의 트러블?이 발생된다. 이때문에 종이로 풀면 왠지 잘 풀리지 않는 기분을 받는것도 이 때문일 수 도 있다. -1을 뺄거라는 생각을 하지 못했는데.... ㅜㅜ

아무튼 해결 했다. 다른 예제에서는 재귀를 통해 풀었지만, 모든 재귀는 반복문으로 바꿀수있다고 생각해서 반복문으로 바꿨다. 또한 이 문제는 음수도 가능하기 때문에 조건도 !=을 활용해 넣었다.

보면 n-stoi("1")가 있는데 그냥 1을 빼면 되지 않을까 라는 생각을 할 수 있다. 이걸 하는 이유는 의도적으로 넣었다.(안넣어도 되는데...) 이렇게 해서 1값을 빼는데, 그게 "1"이 추가 된다는걸 강조 하기 위해 한 행동이라 보면 된다. 그냥 1넣어도 답은 같다. (어쩌면 의미 없는... 성능에 불 필요할 수 도...)

 

왜 리버스를 했냐면... 반복문은 스택형식이지만 이건 호출하는데로 보여주기때문에 값이 반대로 나온다. (난 이게 좋더라.)

 

#include <stdio.h>
void solve(int N, bool isNegative) {
	if (N == 0)
		return;
	if (N == 1 && !isNegative) {
		printf("1");
		return;
	}
	if (N == 1 && isNegative) {
		printf("11");
		return;
	}
	if (N % 2 == 0) {
		solve(N / 2, !isNegative);
		printf("0");
	}
	else {
		if (!isNegative) // 다음 digit은 negative
			solve((N - 1) / 2, !isNegative);
		else
			solve((N + 1) / 2, !isNegative);
		printf("1");
	}
	
}
int main(void) {
	int N;
	scanf("%d", &N);
	if (N == 0)
		printf("0");
	else
		solve(N, 0);
}

- by BaaaaaaaaaaarkingDog