[백준] 2089 : -2진수 JAVA 풀이

 

 

음..자꾸 오답 판정이 나와서 다른 사람들의 풀이과정을 참고했다.

 

예제 입력에 나온 -13은 

-13 = (-2) * 7 + 1

7 = (-2) * 3 + 1
-3 = (-2) * 2 + 1
2 = (-2) * (-1) + 0
-1 = (-2) * (1) + 1
1 = (-2) * 0 + 1

이렇게 풀어볼 수 있다.

노란색으로 표시한 숫자를 아래부터 읽으면 110111

예제 출력과 일치하는 것을 확인할 수 있다.

 

여기서 첫 번째 식에 주목하자.

사실 -13 / -2를 계산하면 몫이 6이 되고 나머지가 -1이 되어

-13 = (-2) * (6)  + (-1)이 된다.

하지만 -2진수는 각 자리에 0또는 1만 올 수 있기 때문에 문제가 발생한다.

따라서 이렇게 n % -2의 결과가 -1인 경우에는

몫에 +1을 해주고 나머지를 1로 바꿔줘야 한다.

 

import java.io.*;
import java.util.*;
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());
		
		StringBuilder sb = new StringBuilder();
		
		if(n==0) {
			System.out.println(n);
			return;
		}
		
		while(n!=0) {
			if(n%-2==-1) {
				sb.append(1);
				n = (n/-2)+1;
			}
			else {
				sb.append(n%-2);
				n = (n/-2);
			}
		}
		System.out.println(sb.reverse());
	}

}