[백준] 2089번 (python 파이썬)

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

2089번: -2진수

 

number = int(input())
if number == 0 :
  print(0)
else:
  d = number
  result = ""
  while d != 1:
    r = d % -2
    d = d // -2
    if r < 0:
      d += 1
      r *= (-1)
    result += str(r)
  else:
    result += str(d)
  print(result[::-1])

 

 

2진법을 구할땐 십진수를 2로 나누고 나머지를 거꾸로 출력한다.

-2진법을 구할땐 십진수를 -2로 나누고 나머지를 거꾸로 출력한다. 

단! -2로 나눌땐 나머지는 항상 양수여야 한다.

즉, -13을 -2로 나누면 몫이 6, 나머지가 -1 이 아니라, 몫이 7, 나머지가 1 이어야 한다.

 

또한 입력값의 범위가 -20억부터 20억 까지다.

리스트 자료형을 사용하기엔 메모리가 너무 크다.

리스트 요소 하나당 대략 4바이트라 생각할때 최대 8기가바이트가 사용된다.

따라서 시간복잡도가 좋지 않음에도 문자열 자료형을 사용하기로 한다.

 

입력값이 0일 경우는 따로 빼주어야 한다.

이 부분을 찾지 못해서 시간을 많이 소모했다.