백준 1011 : Fly me to the Alpha Centauri (파이썬)

 

문제

https://www.acmicpc.net/problem/1011 문제풀이

 

 

 

 

---

코드

import sys
for _ in range(int(sys.stdin.readline().rstrip())) :
    x,y = map(int,sys.stdin.readline().split())
    distance = y-x
    sqrtDistance = distance**.5
    movecnt = int(sqrtDistance)*2 - 1
    # 거리가 제곱근일 경우
    if sqrtDistance%1 == 0 :
        print(movecnt)
    # 거리의 제곱근의 소수점 부분이 0.5 이하일 경우
    elif sqrtDistance%1 < .5 :
        print(movecnt+1)
    # 거리의 제곱근의 소수점 부분이 0.5이상일 경우
    elif sqrtDistance%1 > .5 :
        print(movecnt+2)

코드 풀이

오랜시간 고민을 해봤는데 규칙이 도저히 없어 보였다...

그래서 x좌표와 y좌표에 상관없이 거리에만 값이 달라지므로 y-x를 거리로 두고 하나씩 전부 적어 봤다!

처음에는 거리 제곱근을 안 적어두어서 규칙을 찾지 못하다가 거리의 제곱근을 추가하는 순간 규칙이 보이기 시작했다.

바로 제곱근의 소수점에 따라 결정되는 규칙!!!!!

3가지 경우의 수가 존재했는데 

 

1. 거리의 제곱근의 소수 부분이 없을 경우!! 즉, 거리가 정수의 제곱일 경우!!!

해당 경우에는 단순한 게 "거리 제곱근*2 -1"을 취해주면 값이 나왔다

 

2. 거리의 제곱근의 소수 부분이 0.5 미만일 경우!!

1번 경우에서 +1 해주면 된다.

 

3. 거리의 제곱근의 소수 부분이 0.5 초과일 경우!!

1번 경우에서 +2 해주면 끝!!

 

---

거리의 제곱근의 소수 부분이 0.5일 경우는 어떻게 처리해야 하는가???

사실 이경우는 고려하지 않아도 된다. 왜냐?? 입력의 제한사항 안에서 가장 큰 값인 2의 31 제곱의 소수점인데 이경우에서도 0.5를 기준으로 나눠지기 때문이다.

그러므로 걱정하지 않아도 된다!!

 

이런 간단한 방법이 있을줄이야... 역시 규칙을 찾을수없을땐 하나하나 다 써보는게 도움이 된다!!