백준 1011 [파이썬 알고리즘] : Fly me to the Alpha Centauri

 

[Python] 백준 알고리즘 온라인 저지 1011번 : Fly me to the Alpha Centauri

 

Python3 코드

t = int(input())

for _ in range(t):
    x, y = map(int,input().split())
    distance = y - x
    count = 0  # 이동 횟수
    move = 1  # count별 이동 가능한 거리
    move_plus = 0  # 이동한 거리의 합
    while move_plus < distance :
        count += 1
        move_plus += move  # count 수에 해당하는 move를 더함
        if count % 2 == 0 :  # count가 2의 배수일 때, 
            move += 1  
    print(count)

 

 

Python3 코드 풀이

백준 알고리즘 1011

1. 표에 대한 설명 

위 표는 이 문제를 풀 때 필요한 거리, 경로, 이동 회수를 정리한 표이다. 위 표에서 보면 이동 회수 (count)의 숫자가 증가할 때 일정한 규칙을 갖고 증가하는 것을 볼 수 있다. 

 

이동 회수(count)를 보면 1이 1번, 2가 1번, 3이 2번, 4가 2번, 5가 3번, 6이 3번 이런 식으로 나타나는 것을 볼 수 있다. 즉 이동 회수를 나타내는 숫자의 빈도수가 1,1,2,2,3,3,4,4, 이런 식으로 두 번씩 나타나는 규칙을 찾을 수 있다.

 

이 빈도수에 해당하는 수를 더한 합은 count 숫자에 따라 이동 가능한 최대 거리를 나타낸다. 예를 들어 count가 6을 나타낸다면 count 6까지 우측 move distance 숫자를 합하면 12가 된다. (1+1+2+2+3+3 = 12) 

 

위와 같은 이동회수의 빈도수와 이동거리 증가의 규칙성을 이용해서 문제를 풀었다.

 

2. 코드 상단부 설명. for반복문 안에서 변수를 선언한다.

for _ in range(t):
    x, y = map(int,input().split())
    distance = y - x
    count = 0  # 이동 횟수
    move = 1  # count별 빈도수
    move_plus = 0  # 이동한 거리의 합

맨 처음 테스트케이스테스트 케이스 수를 입력받은 후 테스트 케이스 수만큼 for문을 반복한다. 

 

두 번째로 현재 위치와 목표위치를 입력받으면 x, y 변수로 저장한다. 이 변수를 입력받고 실질적으로 이동해야 하는 거리를 구하기 위해서 목표 위치인 y에서 현재 위치 x를 뺀 수를 distance라는 변수에 선언한다.

 

이외에 count는 이동 횟수를 나타내기 위한 변수이고 move는 이동 횟수의 빈도수를 나타내기도 하며 count 회수 별 이동할 수 있는 최대 이동거리를 의미한다. move_plus는 count별 move를 합한 수로 반복문이 반복하는 동안 총 이동한 거리를 나타낸다.

 

3. 코드 while문 설명. 이동 회수를 구할 수 있는 while문을 반복한다.

    while move_plus < distance :
        count += 1
        move_plus += move  # count 수에 해당하는 move를 더함
        if count % 2 == 0 :  # count가 2의 배수일 때, 
            move += 1  
    print(count)

while 반복문은 처음에 입력 받은 목표 위치 y에서 현재 위치 x를 뺀 distance 변수가 while문을 반복하면서 이동거리 증가 수 move_plus 보다 큰 경우에만 반복한다.

 

count 변수는 while 문이 반복되는 동안 1씩 증가한다. 그리고 move는 count가 증가할 때마다 증가하는 이동거리를 의미한다. 즉, count가 증가할 때마다 해당 count에 따라 이동할 수 있는 거리를 합해가면서 처음에 입력받은 이동거리 distance에 도달하면 반복문을 멈춰서 count를 구하는 방식이다.