99클럽 코테 스터디 13일차 TIL - 고양이는 많을수록 좋다(백준 #27961)

❇️오늘의 학습 키워드 : 고양이는 많을수록 좋다(백준 #27961)

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

1

예제 입력 2 

6

예제 출력 2 

4

 

예제 입력 3 

2147483648

예제 출력 3 

32

원하는 고양이의 수가 32bit 정수형 범위를 벗어날 수 있음을 주의하라.

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
cat = 1
cnt = 0

if n == 0:
    print(0)
elif n == 1:
    print(1)
else:
    while True:
        if cat*2 >= n:
            cnt += 1
            break
        else:
            cat *= 2
            cnt += 1
    print(cnt+1)

❇️오늘의 회고

  - 맨 마지막 프린트문 들여쓰기를 안해서 잠시 삽질했다...설마설마했는데 진짜...ㅎㅎ

  - 처음만 생성하고, 나머지는 다 복제로 처리하는 것이 제일 효율적이다!

  - 내일 11시, 문제를 풀기 전에 위 문제를 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂