백준 2089번 - -2진수 (Java 8)

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

2089번: -2진수

코드 :

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));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        if(N == 0){
            sb.append(0);
        } else{
            while (N != 1){
                sb.append(Math.abs(N % -2));

                N = (int)(Math.ceil((double)N/-2));
            }
            sb.append(N);
        }
        System.out.println(sb.reverse());
    }
}

 

풀이 : 

결국 답보고 겨우 풀었고, 이해도 완벽하지 않다. 2진수 구하는 법과 거의 같긴한데, 무언가 마음 한구석이 찝찝하다.

 

-13을 예시로 하면,

 

-13 = (-2*7)+1

7 = (-2*-3)+1

-3 = (-2*2)+1

2 = (-2*-1)+0

-1 = (-2*1)+1

1

 

와 같이 나타낼 수 있다. (110111)

잘 보면 -2로 나누었을 때 몫을 올림한 값이, 다음에 나누어지는 수가 되는 걸 알 수 있다.

ex:

-13/-2 = 6.5 -> 7

7/-2 = -3.5 -> -3

 

결국 나머지를 양수로 만들기 위해, 몫을 올림처리 하여 다음 나누는 수로 만들면 깔끔하게 해결된다는 의미이다. 또한 애초에 N이 int형 이기 때문에, 나머지에 절대값을 씌워주면 나머지가 양수가 된다.

 

주의점 :

• 0처리를 따로 해줘야 한다.
• 형변환에 주의하지 않으면 원하는 값을 얻을 수 없다. 예시로 int형인 N/-2를 ceil하면 소수자리가 이미 없어서 아무 의미 없기 때문에, 중간에 나눌때 double로 형 변환해야 한다.
• N값을 음수(-2)로 나누기 때문에, while애매한 부등호 말고, N!=1로 써주어야 한다. 

 

참고 :

https://bellossimo.tistory.com/56