[백준알고리즘] 2089번: -2진수 -Python

[백준알고리즘] 2089번: -2진수 -Python

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

2089번: -2진수

처음 푼 코드는 내가 직접 찾은 방법이다... 창피하긴 한데 풀 때는 다 이렇게 푼 줄 알았다. 먼저, 내가 직접 문제를 해결한 방법을 설명하고 다음으로 대부분 사용한 전형적인 진수 계산법을 설명하겠다.

 

1. 내가한 방법

우선 처음 풀었던 방법은 N이 양수면 N보다 클 때까지, N이 음수면 N보다 작을 때까지 -2 제곱승을 구해준다. 그리고 각 횟수의 제곱이 포함되었을 때 나타낼 수 있는 최댓값과 최솟값을 저장했다. 즉 정리하면 다음과 같다.

 

주어진 예제 -13에 대해서는 음수가 주어졌기 때문에 -13보다 작은 제곱의 결과값이 나올 때까지 구해준다.

[1, -2, 4, -8. 16. -32]

 

여기서 각 제곱승의 값이 더해졌을 때 (1로 표현이 될 때) 갖을 수 있는 최댓값과 최솟값을 구한다. 다음과 같이 될 것이다.

1   -> max:1 min:1

-2  -> max:-1 min:-2

4   -> max:5 min:2

-8  -> max:-3 min:-10

16  -> max:21 min:6

-32 -> max:-11 min:-42

 

이제 -13이 -32가 갖는 범위 안에 들어가기 때문에 -32를 포함해서 계산이 가능한 범위 안에 존재한다는 것이다. 그래서 -32는 포함시키고, 결과에 1을 추가한다. 그리고 현재 값은 -13-(-32)=19가 된다. 이 19 또한 16이 갖는 범위 안에 들어가기 때문에 16을 갖는 것으로 할 수 있게 된다. 현재 값을 19-16=3으로 경신해준다.

여기서 이제는 현재의 값 3이 -8의 범위에 들어가지 않기 때문에 -8을 포함시키지 않고 결과에 0을 추가한다. 그리고 현재의 값 3은 그대로 유지한 채로 4가 포함되는 범위에 들어갈 수 있기 때문에 4를 추가해준다.

 

이러한 방식으로 범위 안에 현재 값이 들어가게 되면 해당 지수승의 값을 더해서 값을 표현할 수 있기 때문에 해당 지수승을 포함시켜주었다.

 

이러한 아이디어를 가지고 문제를 해결했다. 참고로 범위의 max를 유지하기 위해서는 이전 양수들의 총 합과 현재의 값을 더해주었고 min을 유지하기 위해서는 이전 음수들의 총 합과 현재의 값을 더해주는 것으로 구했다. 이 부분은 DP처럼 구성되었다.

import sys

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

power = [0, 0, 1]
max_table = [0, 0, 1]
min_table = [0, 0, 1]
while (N < 0 and power[-1] > N) or (N > 0 and power[-1] < N):
    if N <= max_table[-1] and N >= min_table[-1]:
        break

    power.append(power[-1] * (-2))
    if power[-1] > 0:
        max_table.append(max_table[-2] + power[-1])
        min_table.append(min_table[-1] + power[-1])
    else:
        max_table.append(max_table[-1] + power[-1])
        min_table.append(min_table[-2] + power[-1])

res = ''
now = N
for idx in range(len(power)-1, 1, -1):
    if max_table[idx] >= now and min_table[idx] <= now:
        res += '1'
        now -= power[idx]
    else:
        res += '0'

sys.stdout.write(res)

 

2. 대부분의 방법

문제를 풀고 다른 분들의 코드를 보게 되니 전형적인 진수 계산법을 사용하셨다. 이 방법을 왜 생각 못했을까..? 방식은 간단하다. 마찬가지로 주어진 예제인 -13에 대해 생각해보면 다음과 같이 나타낼 수 있다.

-13 = -2*(7) + 1

 

즉, -2로 나눈 몫이 7, 나머지가 1인 것이다. 나머지는 항상 양수이기 때문에 이러한 방식으로 나오게 된다. 그다음 2진수를 구하듯이 몫에 대해서 -2로 계속 반복해주면 아래처럼 정리할 수 있다.

-13 = -2*(7) + 1

  7  = -2*(-3) + 1

 -3  = -2*(2) + 1

  2  = -2*(-1) + 0

 -1  = -2*(1) + 1

  1  = -2*(0) + 1

 

따라서 110111이라는 주어진 예제에 대한 출력이 정상적으로 나오는 것을 확인할 수 있다. 이 아이디어를 이용한 코드는 아래와 같다.

 

여기서 -2로 나눠 떨어지지 않는 경우 N//-2를 한 후에 +1을 해주는 이유는 -13/-2 = 6.5 이기 때문에 -13//-2 = 6로 출력하기 때문에 몫을 구해주기 위해서는 +1을 해주어서 나머지가 양수가 되도록 해야 한다. 사실 몫을 구하기 위해서는 int(-13/-2) = 7 도 가능하다.

import sys

N = int(sys.stdin.readline())
if not N:
    sys.stdout.write('0')
    exit()
res = ''
while N:
    if N%(-2):
        res = '1' + res
        N = N//-2 + 1
    else:
        res = '0' + res
        N //= -2
        
sys.stdout.write(res)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다