[구현/수학] 백준 27961 고양이는 많을수록 좋다 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

생성마법: +1
복제마법: 1 ~ 2배

 

 마법을 최소로 사용해서 고양이를 N마리로 만들어야 합니다.

 보통 이런 문제는 DP를 사용하지만, 이 문제는 당연히 복제마법의 효율이 좋습니다. 사실상 생성마법 ∈ 복제마법인 셈이죠. 맨 처음에만 생성마법으로 +1을 시키고, 그 다음에는 복제마법만 쓰면 됩니다.

 

 

3. 코드

import sys
import math
input = sys.stdin.readline

# 입력
n = int(input())

if n == 0:
    print(0)
elif n == 1:
    print(1)
else:
    # log2
    res = math.ceil(round(math.log(n, 2), 10))
    print(res+1)

 정밀도가 너무 높으면 오히려 오차가 나는 듯합니다. 로그함수를 사용할 때, 정밀도를 10으로 제한해줍니다.