백준 27961번: 고양이는 많을수록 좋다 (이진법?)

백준 27961번: 고양이는 많을수록 좋다

생성마법: +1
복제마법: 가장 적은 횟수만에 늘려야하므로 *2


가장 적은 횟수로 많은 고양이들을 만들려면
A. 처음에 생성마법 1번,
B. 이후 복제마법으로 2씩 곱해 최대한 N에 가깝게 키운 후
C. 나머지를 1번의 복제마법으로 더한다.

A: N=0이면 0, 이외에는 무조건 1
B: N이 2의 몇 제곱보다 작거나 같으면서 가장 가까운지
C: 제곱하고 남는 수가 있는지


나는 N을 이진법으로 변환해서 풀었다.

파이썬에서 int를 이진법으로 변환해주는 함수 bin을 테스트해보니

• bin(6)=0b110
• len(bin(6))=5

였다. 6은 8(2의 3제곱) 이하이면서 가장 가깝기 때문에
복제마법 B를 3번 사용해야 하는데, len을 쓰면 0b 때문에 2가 더 붙는 것을 확인할 수 있었다.

이를 이용해서 B는 len(n) - 2


n이 8이었다면 1번의 생성마법과 3번의 복제마법 이후에는 더 복제를 하지 않아도 되겠지만, 2의 제곱수가 아닌 경우 다음으로 큰 제곱 수만큼 채워주는 복제 마법 C가 1번 더 필요하다.

2의 제곱인 경우:
8=0b1000, 16=0b10000, ...
0b 뒤 첫째자리만 1이고 그 뒤론 0이다

2의 제곱이 아닌 경우
= 이진수로 나타낸 셋째 자리 후 (bin(n)[3:])가 000...이 아닌 경우
= 0이 몇 개 오든 int(0)/int(000)은 0이므로
bin(n)[3:] == int(0)으로 나타낸다.

이 때, 0b1은 [3:]이 없어서 int를 적용할 수 없기 때문에 예외를 둔다.

n = int(input())

if n == 0:		# A
    print(0)
elif n == 1:
    print(1)

else:
    n = bin(n)
    if int(n[3:]):		# B, C
        print(len(n) - 2 + 1)
    else:				# B
        print(len(n) - 2)