📜문제 설명

문제 바로가기

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

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

• 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
• 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.

마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!

📍입력

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

6

📍출력

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

4

---

📄문제 해결

📝내가 푼 코드

# PyPy3 메모리: 108384KB 시간: 92ms
# Python3 메모리: 32412KB 시간: 40ms

N = int(input())

answer = 0
k = 0

while N > k:
    if k == 0: # 고양이가 없을 경우, 생성
        k += 1
    else:      # 고양이 복제 (0마리 이상, k마리 이하 생성)
        k += k
    answer += 1

print(answer)

이 문제는 복제 마법이 0마리 이상, k마리 이하의 고양이를 소환할 수 있다는 점을 생각하면 간단히 풀 수 있다.

처음에는 고양이가 아예 없으므로 생성 마법으로 한 마리를 소환하고, 그 이후로는 복제 마법만 사용한다. 복제 마법은 최대로 k마리씩 소환하는 것을 반복하다가 N-k가 k보다 작아졌을 때 마지막으로 N-k마리를 소환하는 복제 마법을 사용하면 끝난다.

---

🤔느낀점

이 문제를 처음 맞닥뜨렸을 때는 어떻게 하지? 막막하다가도 생각하다 보니 실마리가 풀렸다. 그리디 문제는 풀 때마다 느끼는 것이지만, 이처럼 하나의 실마리만 찾으면 빠르게 풀리는 것 같다는 생각이 들었다.