[BOJ 20954, Python 3] 택배 기사 민서

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

20954번: 택배 기사 민서

 

풀이

일단 x = 2의 거듭제곱 수만 살펴보면 아래와 같은 수열이 나옵니다.

http://oeis.org/A048487

A048487 - OEIS

 

5 * 2 ** n - 4를 토대로 이어서 생각해보면 일단 x의 다음 항인 x가 음수일 떄의 경우엔 현재 위치가 2 ** n인데, 다음 항의 위치는 - 2 ** n이므로 x = - 2의 거듭제곱 수라면 5 * 2 ** n - 4 + 2 ** (n + 1)로 생각할 수 있습니다.

 

이제 x의 값이 부호를 막론하고 2의 거듭제곱 수가 아닐 때를 살펴봅시다.

 

제 코드를 기준으로 말하면 2의 지수를 구하는 방법은 while 2 ** expo < abs(x) : expo += 1을 하여서 2 ** expo >= abs(x) 꼴이 나오게 만들었습니다.

그러면 만약 x = 5이면 expo = 3으로 2 ** 3 = 8이 나오는 것이죠.

이러면 원래 도달하지 말아야할 x = 8 부분에 도착했으니 2 ** 3만큼 빼주어 원점으로 돌아가서 x만큼 더해주면 됩니다.

그러면 공식이 아래와 같이 나옵니다.

 

 

x가 음수일 때도 똑같습니다. 만약 x = -5이면 expo = 3으로 2 ** 3 = 8이 나오게 됩니다.

이러면 -8로 이동하니까 양수일 때와 똑같이 원점으로 돌아가서 x만큼 더해주면 됩니다.

그러면 공식이 아래와 같이 나옵니다.

 

 

참고로 x = 0일 때 답은 0이니 이것만 주의해주시면 됩니다.

 

 

코드

input = __import__('sys').stdin.readline
for _ in range(int(input())):
    x = int(input())
    expo = 0
    while 2**expo < abs(x): expo += 1
    if x == 0: print(0)
    elif x > 0: print(5 * 2 ** expo - 4 - (2**expo - x))
    else: print(5 * 2 ** expo - 4 + 2 ** (expo+1) - (2**expo - abs(x)))