[Python] 백준 1011 Fly me to the Alpha Centauri

문제 바로가기

   문제분석   

# 이동을 앞뒤로 한칸씩 밖에 못한다.

# 시작과 도착 직전에는 한칸밖에 못움직인다.

# 최소한의 작동횟수로 이동해야하므로 1씩 커지다가 대칭으로 1씩 줄어들게 움직인다.

# 총 n번의 횟수로 갔다고 가정할 때, n-1번째 이동한 거리는 최대 2광년, n-2번째에 이동한 거리는 최대 3광년, n-3번째에 이동한 거리는 최대 4광년......

# 이런식으로 규칙을 찾아야 한다.

거리	최단루트	최소이동횟수
1	1	1
2	11	2
3	111	3
4 (2의 제곱)	121	3 (2*2-1)
5	1211	4
6	1221	4
7	12211	5
8	12221	5
9 (3의 제곱)	12321	5(3*2-1)
10	123211	6
11	123221	6
12	123321	6
13	1233211	7
14	1233221	7
15	1233321	7
16 (4의 제곱)	1234321	7(4*2-1)

# 거리가 어떤 수의 제곱이 나왔을 때, 최소이동 횟수는 해당 수의 제곱근에 2를 곱하고 -1을 한 값이다.

 

 

   문제풀이   

import math

case_number = int(input())

count = 0
result = []

for i in range(case_number):
    a, b = map(int, input().split())

    distance = b - a 
    square_root = math.floor(math.sqrt(distance))
    squared = square_root ** 2

    if distance <= 3: 
        count = distance

    elif distance == squared:
        count = (square_root * 2) - 1

    elif squared < distance <= square_root + squared:
        count = (square_root * 2)

    elif square_root + squared < distance:
        count = (square_root * 2) + 1
    result.append(count)

for k in result: 
    print(k)

# 테스트 케이스를 입력값으로 받고, 이동횟수를 셀 변수와 결과값을 담을 리스트를 초기화한다.

# 테스트 케이스 수만큼 반복문을 돌린다.

# 먼저 입력된 값들간의 거리를 구하고, 그 거리의 제곱근을 구한다. (math모듈의 foor함수를 통해 정수만 구한다.)

# 그렇게 나온 제곱근의 제곱수를 다시 변수에 넣고 조건문의 비교연산에 쓴다.

# 조건문으로 거리가 3 이하일때는 거리와 카운트가 같으니 예외처리를 하고,

# elif문으로 제곱수와 거리를 비교해 count를 추가한다.