[JAVA] 백준 (실버2) 2089번 -2진수

링크

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

---

문제 설명

(정답률 45.625%)
-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진수를 출력하는 프로그램을 작성하시오.

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

---

입력 예제

-13

---

출력 예제

110111

---

정답 코드

1. 가령 -13의 경우 다음과 같이 -2로 나누었을때 몫(-13/-2 = 6.5)을 올림한 값을 0이 될때까지 연산을 진행한다.
   $-13 = -2*7 + 1$
   $7 = -2*(-3) + 1$
   $-3 = -2*2 + 1$
   $2 = -2*(-1) + 0$
   $-1 = -2*1 + 1$
   $1 = -2*0 + 1$
   그러므로 입력값이 0이 될때까지 -2로 나누고 매번 올림을 한다.
2. 양수를 음수로 나누었을 때 나머지는 음수가 되고
   $7 \% (-2) = 1$
   $-2 * (-3) + 1 = 7$
   음수를 음수로 나누었을 때는 나머지가 양수가 된다.
   $-13 \% (-2) = -1$
   $-2 * 6 -1 = -13$
   그러므로 나머지의 절대값을 취한다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        if (num == 0) {
            sb.append(num);
        }
		//num이 0이 될때까지 반복
        while (Math.abs(num) >= 1) {
        	//양수의 나머지를 얻기 위해 절대값을 취함
            sb.append(Math.abs(num % -2));
            //num을 -2로 나누고 올림
            num = (int) Math.ceil((double) num / (-2));
        }
        System.out.println(sb.reverse());

    }
}

---

정리

이 문제도 수학 문제라.. 직관적으로 와닿지가 않았다.
예를 이해하고 보니까 쉽지만 어떻게 풀어야 할지 방향이 잡히지 않아서 구글링을 하였다.