[알고리즘] 백준 2089번 -2진수 :: 우유

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

2089번: -2진수

 

---

단순한게 최고라는 생각에 일반적인 2진법으로 나누었을때랑 같은 방법으로 -2를 나누어보았다.

예를들어

-13 / -2 = 6.5 -> 올림 7 (나머지 1)

7 / -2 = -3.5 -> 올림 -3 (나머지 1)

-3 / -2 = 1.5 -> 올림 2 (나머지 1)

2 / -2 = -1 -> -1 (나머지 0)

-1 / -2 = 0.5 -> 1 (나머지 1)

1. 마지막 몫이 1일때까지 반복되야 함.

2. 나머지는 항상 양수

3. 음수에서 계산이 되기때문에 소수점에서 올림 (ceil)

4. 마지막 1일때 몫을 따로 append 해주고 순서를 reverse 해야한다. 

위와 같은 방법으로 코드를 구현하였다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		int N = Integer.parseInt(br.readLine());

		if (N == 0) {
			System.out.println(0);
		} else {
			while (N != 1) {

				sb.append(Math.abs(N % -2));
				N = (int) Math.ceil((double) N / (-2));

			}

			sb.append(N);

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

	}
}