BOJ 2089 -2진수 [Java]

BOJ 2089 -2진수

1. 문제 링크

https://www.acmicpc.net/problem/2089

2. 문제 해설

-2진수도 2진수와 같이 결국 1과 0으로만 표현해야한다.
10진수를 2진수로 바꿔줄 때와 비슷하게 10진수를 -2로 나누어주며 과정이 진행된다.
-2로 나누어주면 나머지가 0 혹은 -1이 나오는데 0의 경우는 2진수와 동일하게 처리가 가능하지만, -1의 경우는 다른 방식이 필요하다.
나머지가 -1인 경우를 어떻게 처리하는지 예시를 들어보겠다.
7을 -2로 나누는 경우를 생각해보자. 7 / (-2) = (-2) x (3) - 1 이다.
이것을 다르게 표현하면, 7 / (-2) = (-2) x (4) + 1 이다.
즉, 나머지가 -1인 경우에는 나머지를 1로 바꿔주고 몫을 1 더해주면 된다.

알고리즘의 흐름을 살펴보자.

1. 입력 받은 n을 -2로 나눈 나머지를 r로 저장한다.
2. n을 -2로 나눈 값을 n으로 저장한다.
3. r이 -1 이면 1로 바꿔주고 n에 1을 더해준다.
4. n이 0이 아니면 1~3 과정을 반복한다.

3. 코드 보기

import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        if (n == 0)
            bw.write('0');

        while (n != 0)
        {
            int r = n % (-2);
            n /= (-2);

            if (r < 0)
            {
                r = r * (-1);
                n++;
            }

            sb.append(r);
        }

        bw.write(sb.reverse().toString());
        br.close();
        bw.flush();
        bw.close();
    }
}