[알고리즘][백준] 2089번 -2진수 - 파이썬(python) 풀이

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

2089번: -2진수

---

 

1 -> 1
2 -> 110 = 4 -2 0
3 -> 111 = 4 -2 1
4 -> 100
5 -> 101
6 -> 11010 = 16 -8 -2
7 -> 11011 = 16 -8 -2 1
8 -> 11000 = 16 -8
9 -> 11001 = 16 -8 1
10 -> 11110 = 16 -8 4 -2
13 -> 11101 = 16 -8 4 1
-13 -> 110111 = -32 16 2 1

 

-2라서 어떻게 푸는가 했는데 2진수나 8진수처럼 똑같이 -2로 값을 나누면 됐었다 결국엔 진수였던것..!

몫이 0이 나올때까지 진행하면 110111이 나오게 된다

-13 ÷ -2 =  7 ... 1

   7 ÷ -2 = -3 ... 1

  -3 ÷ -2 =  2 ... 1

   2 ÷ -2 = -1 ... 0

  -1 ÷ -2 =  1 ... 1

   1 ÷ -2 =  0 ... 1

import sys

from collections import deque

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

result = deque()

while n:

    result.appendleft(n % (-2))

    n //= (-2)

print(*result, sep="")

 

 

나머지에 왜 1이아니라 -1이 나오고 왜 자릿수는 6개가 아니라 5개인가..?

 

확인해보니 2가지 오류가 있었다.
1. 파이썬에서 음수로 나누면 -2의 경우 0, -1이 나와 나의 의도대로 나머지가 나오지 않음

2. -13 // -2 결과가 7이 아니라 6으로 나와 몫에 +1을 해줘야함

 

그렇게 완성된 코드!

import sys
from collections import deque

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

if n == 0:  # 0일때도 입력 필수!
    print(0)

while n:
    if n % (-2):    # 나머지 1일때
        result.appendleft(1)
        n = n//(-2) + 1     # -13 // -2 = 6.5 -> 6이라 +1
    else:           # 나머지 0일때
        result.appendleft(0)
        n = n//(-2)

print(*result, sep="")

2089_-2진수.py

0.00MB