[BOJ 19946 / Python 3] 2의 제곱수 계산하기

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

19946번: 2의 제곱수 계산하기

 

문제에서 2의 제곱을 곱하다가 실수로 1을 빼버리는 순간이 단 한 번 존재한다고 하고, 실수할 때가 언제인지 구하라고 합니다.

풀이는 두 가지가 존재합니다.

첫 번째 풀이

첫 번째는 2의 제곱은 계속 짝수만 나오는데, 1을 빼버리면 그때 한 번 홀수인 값이 존재한다는 것을 이용하는 풀이입니다.

이 경우에는 홀수인지 짝수인지 확인하면서 짝수면 2로 계속 나누면 되지만, 홀수가 나오는 순간부터는 1을 더해주어 원래의 계산식대로 만들어주고, 그때부터 ans = 1부터 시작하여 2를 나눌 때마다 ans += 1을 해줍니다. 이러면 1부터 시작해서 계속 2를 곱하다가 언제 1을 빼줬는지의 순서를 알 수 있게 되기 때문에 답을 출력해주면 됩니다.

n = int(input())
flag = False
ans = 1
while n != 1:
    if n % 2 == 0:
        n //= 2
        if flag: ans += 1
    else:
        flag = True
        n = (n + 1) // 2
print(ans)

 

두 번째 풀이

두 번째 풀이는 모든 경우의 수를 확인하는 방법인데, 2**i - 1부터 시작하여 65 - i번만큼 2를 곱해주면 되는 방법입니다. 이 방법을 사용할 경우 어떤 k가 value = 2**k - 1로 시작하여 value에 65 - k번만큼 2를 곱해주면 N이 나오는 값이 존재하게 됩니다. 그래서 해당 k 값을 찾아주면 됩니다.

n = int(input())
for i in range(65):
    k = 2 ** i - 1
    for j in range(i+1, 65):
        k *= 2
    if k == n:
        print(i)