[백준] 2089번 : -2진수 (Python)

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

 

10진법의 수를 하나 입력 받아서 -2진수를 구하는 문제.

import sys
import math

#input = sys.stdin.readline

N = int(input())

def minus_bin(N):
    
    mbin = ''
    
    if(N == 0): # 0일 땐 0!
        return 0;
    
    while(N != 1):
        
        mbin += str(abs(N%-2)) # 나머지를 더해줌
        N = math.ceil(N/-2) # -2로 나누고 올림
        
    mbin += str(N) # 마지막으로 남은 몫을 더해줌
        
    return mbin[::-1] # 역순으로 return

print(minus_bin(N))

 

 

[문제풀이]

---

 

예) -13의 -2진수 구하기

 

-13 = (-2*7)+1

7 = (-2*-3)+1

-3 = (-2*2)+1

2 = (-2*-1)+0

-1 = (-2*1)+1

 

남은 몫 : 1

 

남은 몫부터 역순으로 (110111)라는 답이 나온다.

이때, 다음에 나누어지는 수는 -2로 나누었을 때 몫을 올림한 값이다.

 

ex:

-13/-2 = 6.5 -> 7

7/-2 = -3.5 -> -3

 

왜냐면 나머지는 무조건 0 혹은 1이여야 하기 때문에, 몫을 올림처리 해주는 것!

나머지는 값을 -2로 %연산을 한 값에 절대값을 씌워주면 구할 수 있다.

 

주의점 :

• 0처리를 따로 해줘야 한다.
• N값을 음수(-2)로 나누기 때문에, while애매한 부등호 말고, N!=1로 써주어야 한다.

 

역순으로 보기 때문에, 남은 몫이 0일때는 0101 이처럼 된다.

즉, 어차피 없어질 수이기 때문에 다음에 나눠질 수가 1이 될때까지 -2진수 연산을 처리한다.

다만, 이건 0이 들어올때는 처리를 못해주기 때문에 0은 따로 처리를 해준다.

 

 

참고 : https://programming-beard.tistory.com/107