[JAVA] 2089번 - -2진수

[JAVA] 2089번 - -2진수

출처 - https://www.acmicpc.net/problem/2089

문제

-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진수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.

출력

첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다.

제한

-2,000,000,000 ≤ N ≤ 2,000,000,000

예제 입력 1 -13

예제 출력 1 110111

< 소스 코드 >

import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int input = Integer.parseInt(br.readLine()); String result=""; if (input == 0) { bw.write(input+""); bw.flush(); return; } while(input != 0){ if(input % -2 == -1){ result = (input % -2) + 2 +result; input = (input / -2)+1; } else { result = (input % -2) + result; input /= -2; } } bw.write(result+""); bw.flush(); bw.close(); br.close(); } }

이 문제는 10진수를 -2진수로 변환하는 문제이다.

이 문제를 해결하기 위해 일단 문제를 이해해야하는데, 사실 이해를 하지 못했다.

주어진 예제입력에서 -13이 -2진수로 변환 시, 왜 110111이 나오는지 아무리 생각해도 이해할 수 없었다.

그래서 다른 분들이 어떻게 해결했는지 참고했다.

일단 주어지 입력에서 -2로 계속 나눠서 나머지를 추출하면 되는데, 이렇게만 해서는 주어진 예제입력에서 맞는 결과를 반환할 수 없다.

-13을 입력으로 예를 들면,

-13 % -2 = -1(음수)가 나온다.

2진수로 변환하려면, 반복해서 -2로 %를 통해 나머지를 추출하고 -2로 나눈 몫을 다시 %를 사용하기 위해 대체한다.

하지만, -13 / -2를 하게되면 -6이 나오며, 이는 음수가 나오기 때문에 정상적인 결과가 나올 수 없다.

여기서 (-13/-2) + 1 을 하게 되면, 7로 양수가 나오며, 정상적으로 과정을 이어나갈 수 있다.

그래서 if문 조건을 통해 입력한 input 변수에 %2를 한 결과가 -1이면 음수이기 때문에, 위와 같은 과정으로 진행한다.

양수이면 2진법 변환하듯이 진행하면 된다.

from http://puzzle-moon.tistory.com/71 by ccl(A) rewrite - 2021-12-24 16:27:29