BOJ 2089 - -2진수

문제

BOJ 2089 - -2진수

정수 N을 -2진법으로 변환하라.

입력

정수 N이 주어진다 (-2,000,000,000 이상 2,000,000,000 이하).

출력

N의 -2진법 표현을 출력한다.

예제

풀이

-2로 나누기를 반복하며 나머지를 역순으로 이어 붙인다.

1. N을 -2로 나눈 나머지가 0이면 해당 자리는 0, 1이면 1이다
2. 나머지가 음수(-1)이면 1로 설정하고 몫에 1을 더해 보정한다
3. N이 0이 될 때까지 반복하고, 결과를 역순으로 출력한다

핵심 아이디어: 음수 진법에서는 나머지가 음수가 될 수 있으므로, n // -2 + 1로 보정하여 나머지를 항상 0 또는 1로 만든다.

코드

n = int(input())
res =''
if n == 0:
    print(0)
    exit()
while n:
    if n % (-2):
        res = '1' + res
        n = n//-2 + 1
    else:
        res = '0' + res
        n = n//-2
 
print(res)

복잡도

• 시간: O(N)
• 공간: O(N)