진수 계산법

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

2089번: -2진수

-2 진수로 변환하는 문제이다.

기본적인 2진법은 자리수 마다 2의 제곱수를 해주는데 -2진법은 -2의 제곱수를 자리해주는 방식이다.

때문에 1,3,5,7 번째 자리 즉 홀수번 째 자리에서는 양수가 나오고, 짝수번 째 자리에서는 음수가 나온다.

이를 잘 조합해서 변환해주면 된다.

처음엔 굉장히 복잡하게 생각했었다. 근데 아무리 생각해도 명쾌한 답이 나오지 않아 결국엔 검색을 했다.

 

내가 얻은 답은

10진수를 [특정 진수]로 변환하는 방법은 

[특정 수]가 어떤 수던 간에

 

"똑같다"

 

즉, 10진수를 [특정 진수]로 나누었을 때 나머지가 있으면 1 없으면 2를 1의 자리부터 차곡차곡 채워주면 된다.

단, 음수 진법일 경우에는 나머지가 있는 경우와 없는 경우가 좀 다르다.

 

example) -13

몫 : -13 // -2 = 6

나머지 : -13 % -2 = -1

이렇게 되는데, 진법 계산을 위해서는 나머지가 항상 양수가 되게끔 계산 방식을 바꿔줄 필요가 있다.

즉 -13 = -2 * 6 - 1 이 아닌

    -13 = -2 * 7 + 1 이 되어야 한다.

또 한번 연산이 복잡해지는 느낌이 드는데,

기존의 수를 대치하는 과정에서만 신경을 써주면 된다.

 

if 나머지가 있을 때:

  1) -2진수 답에  "1"을 더해주기

  2) 나눈 몫에 1을 더해주기

else: #나머지가 없을 때

  1) -2진수 답에 "0"을 더해주기

  2) 몫 구해주기

 

이걸 루프로 돌리면 된다.

 

num = int(input())
answer = "" if num != 0 else "0"
while num:
    if num % (-2):
        answer = "1" + answer
        num = num//(-2) + 1
    else:
        answer = "0" + answer
        num = num//(-2)
print(answer)

내가 한가지 더 깨달은 점이 있다면

난 기존에 2진수를 구할 때

answer += "1" or "0" 을 해준 뒤 마지막 출력 전에 reverse를 진행했다. 할 때마다 시간초과가 날 까봐 조마조마했는데

그냥 저렇게 수식을 바꿔서 앞쪽에 값을 더해주게 했으면 됐었다.

 

난 왜 이리도 멍청할까

 

또 하나의 팁이 있다.

첫 번째 시도에서 틀렸는데

 

알고리즘을 풀다보면 (특히 수학파트 문제에서 종종 발생한다) 100%를 찍고 틀렸습니다가 나오는 경우가 있는데

이건 대부분 입력값이 0일 때를 처리해주지 않아서 발생한다.

0을 잘 처리했는지 고민해보면 해결할 수 있다.

 

 

아주 골때리는 상황을 세 번이나 겪었다.

뭐든 기본에 충실하면 되는 듯 하다.

조금 더 노력하자!