[Python] 백준 2885. 초콜릿 식사

 

문제 링크

 

 

풀이

예를 들어 63은 2진수로 표현하면 1111111이다.

또 63 = 1+2+4+8+16+32 이다.

숫자를 2진수로 표현하면 2의 n 제곱수는 각각 한번 밖에 사용할 수 없다.

 

즉, 초콜릿을 2의 제곱수로 나눠서 특정 수의 크기를 만들 때는

2진수로 표현 했을 때 최소의 수가 등장할 때까지 잘라주어야 그 수를 만들 수 있다.

특정 수를 K라 하면 K를 2의 제곱수들로 나눠서 @ + 2 의 형태가 되면 2짜리 크기의 초콜릿이 나올 때까지 잘라야하고,

@ + 64의 형태가 되면 64짜리 크기의 초콜릿이 나올 때까지 잘라야한다. 

 

K보다 크거나 같은 2의 제곱수(이하 변수 two라고 한다)를 구하고

K와 two를 2진수로 변환한다. ( 여기서 two는 2의 제곱수이므로 1이 하나뿐인 2진수이다. ex) 10000...)

K를 역순회하면서 처음으로 등장하는 '1'을 몇 번 비트연산해야 two의 '1'에 닿을까?

2진수 two의 길이  K를 역순회하면서 등장한 '1'의 인덱스 순서를 빼주면 된다.

 

하나의 예시로 K = 34이라 하면 two = 64이고 이를 2진수로 표현하면

k 역순회 최초 등장 '1'이 two의 1에 닿으려면 '<<' 비트 연산을 5번 해줘야한다.
따라서 K = 34일때 정답은 최소 제곱수 64 와 5

 

 

코드

'''
K를 입력 받고
K보다 큰 최소의 2의 제곱수를 구한다
K를 2진법으로 표현한다
ex) K = 34
최소 2의 제곱수 = 64
K =   100010
64 = 1000000
64를 자른다 -> 비트연산 > 1번 = 32( 1회 )
32를 비트연산 > 4번 = 2( 4회 )

63이면? 1단위까지 잘라야함
즉 2진수에서 최소의 제곱수자리까지 비트연산한다
예제1)
K = 6 이면
2진법으로 표현하면
K = 110
8 = 1000
2번 비트연산
'''
k = int(input())
# 최소의 2의 제곱수로 만들어서 이진수로 변환하기
# bin으로 정수를 2진수화하면 '0b1110' 형태가 되는데
# 4번째 문자부터 끝까지 1이 하나도 없으면 2의 제곱수이다. 
def func(num):
    a = bin(num)
    if '1' not in a[3:]:
        a = a[2:]
    else:
        a = '1'+ '0'*(len(a)-2)
    return a
# k보다 큰 최소 제곱수의 2진수 표현
two = func(k)
# k도 이진수로 표현한다
k = bin(k)[2:]
# k를 역순회하면서 '1'을 찾기
for i in range(len(k)):
    if k[::-1][i] == '1':
        len_k = i + 1
        break
print(int('0b'+two, 2), len(two) - len_k)