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

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

2089번: -2진수

2089 문제는 '1975번: Number Game'와 형태가 비슷한 문제이다.

https://skeo131.tistory.com/55

[BOJ](Python) 1975번 : Number Game

다만 1975번과 다른 점은 k진법에서 k<0일 수 있다는 점이기 때문에 계산하는 방식이 다소 특이하다.

결론을 먼저 말하면 a를 -2진법으로 나눌 때,  a = (-2) * b + 0 형태이면 뒤에 0을 붙이고 백트래킹을 이용해 func(b, -2), a = (-2) * b + 1 형태라면 백트래킹을 이용해 func(b, -2)를 계속 반복한다.  (단, b 뒤는 반드시 +1 또는 +0 이다.)

 

두 가지 예시를 보자.

 

1. 4를 -2로 나누는 경우

func(4, -2)에서, 4 = -2 * (-2) + 0 이므로 return func(-2, -2) + 0

func(-2, -2)에서 -2 = -2 * (1) + 0 이므로 return func(-1, -2) + 0

func (1, -2)에서 1 = (-2) * 0 * 1 이므로 return func(0, -2) + 1

func(0, -2)에서 나누려고 하는 수가 0이면 return '0'

따라서 4를 -2로 나누면 ans = 0100이고 ans[1:]를 출력하여 정답을 확인한다.

 

4를 -2진법으로 변환했을 때의 결과

2. -13을 -2로 나누는 경우

func(-13, -2)에서, -13 = -2 * (7) + 1 이므로 return func(7, -2) + 1

func(7, -2)에서 7 = -2 * (-3) + 1 이므로 return func(-3, -2)  + 1

func(-3, -2)에서 -3 = -2 * (2) + 1 이므로 return func(2, 1) + 1

func(2, 1)에서 2= -2 * (-1) + 0 이므로 return func(-1, -2) + 0

func(-1, -2)에서 -1 = -2 * (1) + 1 이므로 return func(1, -2) + 1

func (1, -2)에서 1 = (-2) * 0 * 1 이므로 return func(0, -2) + 1

func(0, -2)에서 나누려고 하는 수가 0이면 return '0'

따라서 -13를 -2로 나누면 ans = 0110111 d이고 ans[1:]를 출력하여 정답을 확인한다.  

 

-13을 -2진법으로 변환했을 때의 결과

코드는 다음과 같다.

import sys
input = sys.stdin.readline
def solve(n, k):
    if n == 0:
        return '0'
    else:
        if n % 2 == 0:
            return solve(n//k, k) + '0'
        else:
            return solve(n//k+1, k) + '1'


T = int(input())
ans = solve(T, -2)
if ans == '0':
    print(ans)
else:
    print(ans[1:])

7행에서,

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

n을 -2로 나눌 때 python은 나머지를 0과 -1로 보기 때문에 우리가 계산하려는 것과 차이가 발생한다.

print(-13//(-2))
>>> right answer : 7
>>> python answer : 6

print(-13%(-2))
>>> right answer : 1
>>> python answer: -1

단, 짝수 일때는 제대로 동작하므로,

print(-14//(-2))
print(-14%(-2))
>>> 7
>>> 0

홀수 일때는 n//k+1로 백트래킹을 진행하고, 짝수일때는 그대로 진행한다.

 

여기서 백트래킹의 종료조건을 다음과 같이 하였는데,

if n == 0:
    return '0'

따라서 앞서 예시처럼 결과값에 무조건 맨 앞에 0이 추가 된다.

이를 return '' 으로 한다면 본 예시들에선 제대로 동작하지만, 만약 n이 0이라면 ''만을 반환하여 주어진 정답인 '0'과 달라 틀리게 된다.

 

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

n이 0이여서 ans = '0'이라면 그대로 ans를 출력하고,

n이 0이아닌 다른 정수이라면 주어진 값이 ans = '0~' 이므로 ans[1:]만을 출력하여 맨 앞 '0'을 제거한다.