[python] BOJ 1011

풀이에 앞서

내가 boj 문제 풀이를 써도 될 정도로 그렇게 프로그래밍을 잘하는 것이 아니지만 (solved.ac 기준 silver4) 어려운 문제를(내 기준에서) 풀었을 때 마다 한번더 생각을 정리해보고 글을 써보기 위해 글을 써본다 (하찮은 작문 실력이지만 내 글을 보고 도움이 되었으면 좋겠다).

문제의 접근

처음에 이 문제를 봤을 때 이해하는데 있어 시간이 조금 걸렸다. 이 문제는 공간이동 장치 작동 횟수에 따라 행성 간의 거리 범위가 주어진다.

예를 들어, 공간이동 장치 작동 횟수=n, 두 행성간의 거리=d 라고 하면

n=1, 1 d=1 n=1 되는 d의 범위 d=1
n=2, 11 d=2 n=2 되는 d의 범위 d=2
n=3, 121 d=4 n=3 되는 d의 범위 2<d<=4
n=4, 1221 d=6 n=4 되는 d의 범위 4<d<=6
n=5, 12321 d=9 n=5 되는 d의 범위 6<d<=9
n=6, 123321 d=12 n=6 되는 d의 범위 9<d<=12
n=7, 1234321 d=16 n=7 되는 d의 범위 12<d<=16

n의 값에 따라 d의 범위가 정해진다. 위의 n의 값과 d의 관계를 보았을 때 n이 홀수 일때 d의 최댓값이 제곱수이다. 그리고 n이 짝수일때의 d의 최댓값은 n이 홀수 일때의 (d의 최댓값)+($\sqrt d$

파이썬 코드

n = int(input())

for x in range(n):
    x, y = map(int,input().split())
    d= y-x
    s=d
    s**=0.5
    s=int(s)
    s=s**2+s
    if d<2:
        print(1)
    elif d==2:
    	print(2)
    elif d**0.5 == int(d**0.5):
        s=d**0.5
        s=int(s)
        s=2*s-1
        print(s) 
    elif d<=s:
        s=d**0.5
        s=int(s)
        s=2*s
        print(s)
    else:
        s=d**0.5
        s=int(s)+1
        s=2*s-1
        print(s)