[브론즈 II] 백준 19946번 : 2의 제곱수 계산하기 (py)

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

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

2의 제곱수 계산하기

 브론즈 II

 

문제

태영이의 취미는 2의 제곱수를 계산하는 것이다.

태영이는 2⁶⁴ = 18,446,744,073,709,551,616 이라는 것을 알고 있고 직접 2⁰부터 2씩 곱해서 2⁶⁴을 구할 것이다.

하지만 태영이는 2씩 곱하는 와중에 1을 빼버리는 실수를 딱 한 번 해버리고 말았다. (실수는 단 한 번만 하며, 그 후에는 2로 곱하는 계산을 정확하게 수행한다.)

예를 들어, 2¹ = 2로 계산을 잘 하다가 2² = 3으로 계산해버리는 어이없는 실수를 해버리는 것이다.

그렇게 된다면 2³ = 6 , 2⁴ = 12 ... 로 계산하여 점점 오차가 커진다.

태영이가 구한 2⁶⁴인 N이 주어졌을 때, 태영이가 처음으로 실수한 구간을 찾아주자.

 

 

입력

양의 정수 N이 주어진다.

N은 태영이가 2⁶⁴를 계산했을 때 나올 수 있는 수이다.

 

출력

태영이가 처음으로 실수한 구간을 찾아주자.

2^K = 2^K-1로 계산해버렸을 때의 K를 출력하면 된다.

 

제한

• 2 ≤ N ≤ 18,446,744,073,709,551,615 = 2⁶⁴ - 1

 

예제 입력 1

2060

 

예제 출력 1

E6

 

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2013 > 중등부 1번

• 데이터를 추가한 사람: newton08

내 풀이

N = int(input())
K = 64

while (1):
    if(N % 2 == 1):
        break
    N //= 2
    K -= 1

print(K)

 

########################## 문제 풀이 ##########################

# 2^64를 하나 하나 곱하겠다는 뜻인데 계산하던 중간에 값에 실수로 1을 빼서 계산을 이어갔다는 것

# N = N*2, N은 2부터 시작, 그러다 실수로 중간에 N = (N*2)-1을 한 후, N = N*2를 계속해서 구했다는 뜻

# 예를 들어, 2^1 = 2로 계산을 잘 하다가 2^2 = 3으로 계산해버리는 어이없는 실수를 해버린 것

# 그렇게 된다면 2^3 = 6 , 2^4 = 12 ... 로 계산하여 점점 오차가 커진다.

 

# 태영이가 구한 2^64 값은 N이다.

# K를 64부터 시작하여 N을 2로 반복적으로 나누면서 K값을 1씩 빼주며 검사한다.

# N을 2로 나누었을 때 나머지가 1이 되었을 때의 K 값을 구하면 된다.

# 예를 들어 태영이가 2^6를 잘못 구한 경우 N의 값이 56라고 해보자

# K는 6부터 시작하여 검사할 것이고, N을 2로 반복적으로 나누어 보자.

 

K	6	5	4	3
N	56	28	14	7
K%N	0	0	0	1

 

# 제대로 계산 되었을 때의 값

K	6	5	4	3
N	64	32	16	8
K%N	0	0	0	0

 

# 반대로 검산을 해보면

# 2^1 = 2, 2^2 = 4, 2^3 = 8-1, 2^4 = 14, 2^5 = 28, 2^6 = 56 이런식으로 계산을 했다는 것

##############################################################