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

 

제한

• -2,000,000,000 ≤ N ≤ 2,000,000,000

풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // N이 0이면 그대로 0 출력
        if(N == 0) {
            System.out.println(0);
            return;
        }

        StringBuilder sb = new StringBuilder();
        while (N != 0) {
            int remainder = N % -2;     // 나머지
            N /= -2;

            // 나머지가 -1인 경우 1로 변경
            if (remainder < 0) {
                remainder += 2;
                N++;    // 2로 나누어 떨어지지 않았기 때문에 정수 나눗셈을 고려하여 나머지 추가
            }

            sb.append(remainder);
        }

        System.out.println(sb.reverse());

        br.close();
    }
}

 

-2진수는 우리가 알고 있는 2진수와 비슷하게 각 자리를 -2의 거듭제곱으로 표현한다. 문제에서 제시된 예를 토대로 설명해보자면, -6을 -2진수로 표현하면 11010이 된다. 아래 표를 보자.

(-2)⁵	(-2)⁴	(-2)³	(-2)²	(-2)¹
1	1	0	1	0

 

-2의 거듭제곱을 토대로 -2의 제곱이나 네제곱 자리는 양수가 된다. 따라서 이를 계산하면

“16+(−8)+0+(−2)+0=16−8−2=6”

형태가 된다.

 

작성한 코드는 주어진 수를 -2로 나눴을 때 나머지를 기준으로 구분한다. 나머지가 -1인 경우 1로 변경한다. 이는 나머지가 0 또는 1일 때를 취급하기 때문이다. 이는 곧 절댓값이 2로 나누어 떨어지는지 확인하는 과정을 말한다. 음수로 나온 나머지를 보정했기 때문에 이를 반영하여 몫에 반영한다. 2진수 계산과 마찬가지로 계산한 나머지를 reverse() 하여 출력한다.

 

 

출처: 백준, https://www.acmicpc.net/problem/2089