백준 2089 -2진수 (Java)

URL

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

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

생각

• 문제에 주어진 -13은 "-13 = (-2 * 7) + 1"과 같다.

• 7은 "7 = (-2 * -3) + 1"과 같다.

• -3은 "-3 = (-2 * 2) + 1"과 같다.

• 그런데 나머지는 항상 양수이어야함므로(나누어 떨어지지 않았을 때) 몫은 -13/-2의 결과에 올림 처리를 한 셈이다.

 

성공 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int input = scanner.nextInt();

        if (input == 0) {
            System.out.println(0);
        } else {
            while (input != 1) {
                sb.append(Math.abs(input % -2));
                input = (int)Math.ceil((double) input / (-2));
            }

            sb.append(input);

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