[python] 백준 1669 멍멍이 쓰다듬기

1669번: 멍멍이 쓰다듬기 (acmicpc.net)

1669번: 멍멍이 쓰다듬기

문제

원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다.

 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.

 

현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수는?

 

monkey,dog = map(int,input().split())

diff = dog-monkey # 멍멍이와 원숭이의 키 차이

if diff==0:
    print(0)    #키차이가 없으면 0
else:
    n=0
    while n*n< diff: #제곱을 한 게 키차이보다 커지는 순간까지 n 증가
        n+=1
    if n*n != diff: #키차이보다 작은 가장 큰 제곱수 구하기
        n-=1
    result = 2*n-1
    diff -= n*n #제곱한 걸 빼주고 남은 키차이

    while diff>0: #남은 키차이가 있을 때까지
        diff-=min(n,diff) #남은 키, 구한 제곱수 중에 작은 값 빼주기
        result+=1
    print(result)