BOJ 2089 -2진수

https://www.acmicpc.net/problem/2089
시간 2초, 메모리 128MB
input :

• N(-2,000,000,000 ≤ N ≤ 2,000,000,000)

output :

• -2진법 수를 출력

---

어우... 복잡해

나머지는 언제나 양수여야 한다.
이게 제일 중요한듯.

파이썬에서 (n // -2) 를 하게 되면 얘네들은 자동적으로 나머지를 -1을 남긴다.(1이 아닌)
그렇다면 나머지를 양수로 만들어 주려면? 몫을 1을 늘려주면 된다.

-13을 -2 로 나눌 때 나머지를 1을 남기고 싶으면
7 * (-2) + 1 의 형태가 되는 것이다.
원래 -13 // -2 를 하면 6이 된다.
그래서 몫을 1 늘려주는 것.

그리고 언제나 n == 0 이 되면 '0'을 추가하도록 했기 때문에 마지막 출력에서 슬라이싱을 해준다.

import sys

n = int(sys.stdin.readline())


def solve(n):
    if n == 0:
        return '0'
    else:
        if n % 2 == 0:
            return solve(n // -2) + '0'
        else:
            return solve(n // (-2) + 1) + '1'


ans = solve(n)
if ans == '0':
    print(ans)
else:
    print(ans[1:])