[백준] 27961 고양이는 많을수록 좋다

문제

마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 $N$마리를 집에서 키우기로 결심했다!

마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.

생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.
마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!

입력

첫 번째 줄에 키우기를 원하는 고양이의 수 $N(0\leq N\leq 10^{12})$이 정수로 주어진다.

출력

첫 번째 줄에 정확히 $N$마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.

내 풀이

import sys
input = sys.stdin.readline

n = int(input())

# Let's take n = 1*a + 2**b

def power_two(num):
    # num should be 2**N (N = natural number)
    cnt = 0
    while num > 1:
        if num %2 != 0:
            return -1
        num //= 2        
        cnt += 1
    return cnt if num == 1 else -1

a = 0
b = 0
while n > 1:
    c = power_two(n)
    if c == -1:
        a += 1
        n -= 1
    else:
        b = power_two(n)
        break

if n == 0:
    print(0)
else:
    print(a+b)

행동이 1) 고양이 1마리 추가 2) 고양이 수 2배 (정확히는 2승?)여서 $N = 1 \times a + 2^b$ 를 만족하되 a + b가 최소가 되도록 찾는 문제라고 이해했다. 그러다가 유형 힌트가 그리디인 것을 확인하고 더 확신을 가지고 문제를 풀었으나 사실 예제 입출력에서 1 정도 숫자가 차이가 나게 되어서 오답을 제출했다. 심지어 틀렸습니다!도 아니고 시간 초과를 받음...
따라서 해결해야 할 문제는 1) 1 차이가 어디서 발생하는지 2) 시간 초과 해결 이었다. 아래는 다시 풀어서 정답을 받은 코드 (코멘트에서 설명)

import sys
input = sys.stdin.readline

n = int(input())

if n == 0:
    print(0)
else:
    # 2의 거듭제곱 중 n보다 크거나 같은 최소값을 찾기
    power = 1
    cnt = 0
    while power < n:
        power *= 2
        cnt += 1
    print(cnt + 1)  # 첫 1마리를 데려오는 연산 포함

코멘트

claude에게 물어봤는데 너무나도 명확하게 잘못된 점을 짚어준다. 우선 내가 "최소" 횟수라는 조건에 집착해서 고양이가 2배수 되는 것임에도 불구하고 2의 지수승으로 계산하려는 오류를 뒀다. 아예 로직 자체가 잘못된 것이었다.
그러나 claude가 알려준 것처럼 2배수에 도달할 때까지 count를 세고 첫 한 마리를 데려오는 +1을 해주면 간결하게 해결할 수 있고 시간 초과도 뜨지 않는다.

References

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