문제

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 2^0, 2^1, 2^2, 2^3이 표현 되지만 -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진수를 출력하는 프로그램을 작성하시오.

www.acmicpc.net/problem/2089

  • 입력

첫 줄에 10진법으로 표현된 수 N이 주어진다.

  • 출력

-2진법 수를 출력한다.

최종 코드

생각보다 간단한 문제였다. -2진수라는 문제 이름처럼 그냥 숫자를 2 대신 -2로 나누면 되는 문제였다.

-13을 -2진수로 바꾸는 경우

-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 를 계산했을 때 몫으로 7이 아닌 6이 나온다는 점이다. 따라서 나머지가 1인 경우 몫은 +1 해주어야 한다.

n = int(input())

tmp = n
res = ""
while n != 0:
    if n % -2 != 0:
        res = "1" + res
        n = n // -2 + 1
    else:
        res = "0" + res
        n = n // -2

if tmp == 0:
    print(0)
else:
    print(res)

참고 사이트