[Python] 백준1011번 풀이

Fly me to the Alpha Centauri

1.거리에 따른 이동 규칙을 찾는 문제였다. 마지막 거리1을 제외한 나머지 거리를 역으로 탐색하는 방법을 생각했지만 규칙성을 찾아서 해결하는 문제에 옳지 못한 방법이었다.
   타 게시판에서 힌트를 찾을 수 있었는데, 일정 거리를 지속적으로 늘려가다가 결국 마지막 1광년을 가기 위해 어느 시점부터 다시 지속적으로 움직이는 거리를 줄여야 한다는것이다.

2.그렇다면 어느 시점부터 다시 움직이는 거리를 줄이는 것일까?
   이에 대한 해답은 총 이동거리에 따라서 어떻게 움직여야하는지 표를 그려 파악할 수 있었다.

3.위의 표를 살펴보면 제곱수가 되는 K(볼드체가 표시되어 있는 2,3,4….) 를 기준으로 움직인 회수가 바뀌는것을 확인할 수 있다.
   다시말해, 우리가 움직여야하는 거리가 주어졌을 때 가장 가까운 제곱수로 나타낼 수 있는 값 K를 찾아야한다.

1
2
3
4
5

x, y = map(int, input().split())
stand = 0
if math.sqrt(y-x) - math.floor(math.sqrt(y-x)) < 0.5:
	stand = math.floor(math.sqrt(y-x))
else: stand = math.ceil(math.sqrt(y-x))

총 움직여야하는 거리 y-x 에 대해
   sqrt값과 sqrt의 floor값 차이를 구해 이 값이 0.5 보다 작다면 기준이 되는 K값(위의 코드에서는 stand값)은 sqrt의 floor값이라고 할 수 있다.
반대로, 0.5보다 크다면 K값은 sqrt의 ceil값이 될 것이다.

4.기준이 되는 값 K를 구했다면 K와 움직인 횟수와의 관계를 살펴봐야 한다.
   우리가 움직인 거리와 K의 제곱값을 비교하면 알 수 있다.
   만약, y-x가 K의 제곱보다 크다면 움직인 횟수는 K2이며
   y-x가 k의 제곱보다 작거나 같다면 움직인 횟수는 k2-1의 규칙을 따르는 것을 확인할 수 있다.

1
2
3
4

if y-x > stand**2:
	print(stand*2)
elif y-x <= stand**2:
	print(stand*2-1)

Full code

Full code