백준 2089. -2진수

알고리즘 기초 문제 중 수학1 연습 문제(301)

-2진수

1. 간단 설명

---

10진수가 주어졌을 때, 이를 -2진수로 변환하여 출력하는 문제

음수 진법에 대한 상세 설명은 여기를 참조

2. 문제 분석

---

-2진수라는 표현이 생소할텐데, 다른 진법 변환처럼

-2로 해당 수를 1이 남을때 까지 계속 나누어 1이 나머지를 확인하면 된다.

예시

10진수 -13을 -2진수로 변환하는 방법

필요 변수

• int n (-2,000,000,000 ≤ N ≤ 2,000,000,000)
• 변환 결과를 저장할 문자열 res

주의사항

• n은 0도 가능하다

알고리즘

1. n을 입력받는다
2. n이 0인지 확인 후, 0이라면 0을 출력 후 종료
3. 0이 아니라면, 0이 될때까지 -2로 나누면서 다음을 반복한다
	3-1. 만약 -2으로 나누어 떨어진다면, res의 맨 앞에 0을 추가한뒤, n을 -2로 나눈다
	3-2. -2으로 나누어 떨어지지 않는다면, res의 맨 앞에 1을 추가한뒤, n에 (n-1)을 -2로 나눈 값을 저장한다

3-2에서 n이 아닌 n-1을 나누는 이유는

python과는 다른 C,C++의 특성으로 발생하는 차이 때문이다.

예를들어 7/-2의 결과값인 -3.5를

python에서는 -4로 소수점을 내리고(그 수보다 작은 정수로),

C에서는 -3으로 소수점을 버리게 된다

-2진수를 구하는 경우, 내림 방식을 취해주어야 정확한 값을 계산할 수 있기 때문에

n이 홀수인 경우에는 내림을 할 수 있도록 (n-1)/-2로 계산한다

3. 소스코드

---

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int main() {
	int n;
	cin >> n;

	if (n == 0) {
		cout << 0;
		return 0;
	}

	string res;

	while (n != 0) {
		if (n % -2 == 0) {
			res = '0' + res;
			n /= -2;
		}
		else {
			res = '1' + res;
			n = (n - 1) / -2; // 버림을 보완하기 위해 -1을 해줌
		}
	}

	cout << res;

	return 0;
}

음수 진법을 다루어본 문제는 이번이 처음이였는데, 진법 변환이 꽤 햇갈렸다

이와 관련된 문제들을 많이 풀어봐야겠다

참조

[BOJ][C++] 백준 2089번 -2진수