백준 1011번 풀이(파이썬)

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

 

문제 이해하는데 한참걸렸다. 결국 구글링해서 무슨뜻인지 알아냈고 많은 분들의 포스팅을 보고 규칙을 확인하였다.

 

문제에서 조건상 가장 마지막 이동거리는 1로 고정적으로 들어가야 한다고 했다.

 

문제에서 이동거리를 한번에 늘릴수도 줄일수도 없게 설정이 되어있다. 무조건 한칸씩 늘리거나 줄이란다. (+1 or -1)

 

그래서 거리좀 벌린다 싶으면 다시 줄여야 하는 포물선같은 형태가 나오게 된다.

 

 

 

잘 보면 총 4구간으로 나눌 수 있고 거리가 4보다 커지는 순간 2, 3, 4 구간이 반복되는 것을 알 수 있다.

 

그럼 이제 입력한 값들사이의 거리에 따라 반복패턴 중 어디구간에 속해 있는지 확인만 되면 쉽게 최소 이동 횟수를 구할 수 있다.

 

import math

N = int(input())

count = 0                                    #최소 작동 횟수
result = []

for _ in range(N):
    a, b = map(int, input().split())
    distance = b - a                         #주어진 값들간의 거리

    num = math.floor(math.sqrt(distance))  #주어진 값들 사이의 거리에 루트 씌움 (제곱근) , floor처리되어 이미 정수임    
    num_jegob = num**2                # 정수를 제곱근으로 갖는 제곱수(ex. 9 : 9의 제곱근은 3)

    if distance == num_jegob:
        count = (num*2)-1

    elif num_jegob < distance <= num_jegob + num:
        count = (num*2)

    elif (num_jegob + num) < distance:
        count = (num*2) + 1

    elif distance < 4:
        count = distance
    result.append(count)



for x in result:
    print(x)

 

 

math.floor : 내림 기능
  -> 3.xxxxx 전부 3으로 만들 수 있음 int로 해줘도 되긴함 근데 새로운거 쓰면서 배우는게 더 좋으니까