[백준/Python] 1011_Fly me to the Alpha Centauri

문제

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

풀이

이 문제는 distance(행성 사이 거리)가 1인 경우부터 차근차근 구해봐야 일정한 규칙을 발견할 수 있습니다.

path: 이동 경로

cnt: 최소한의 공간이동 장치 작동 횟수

same_cnt_times: 같은 cnt가 연속된 횟수

distance	path	cnt	same_cnt_times	행의 갯수
1	1	1	1	2
2	11	2	1
3	111	3	2	4
4	121	3
5	1211	4	2
6	1221	4
7	12211	5	3	6
8	12221	5
9	12321	5
10	123211	6	3
11	123221	6
12	123321	6
13	1233211	7	4	8
14	1233221	7
15	1233321	7
16	1234321	7
17	12343211	8	4
18	12343221	8
19	12343321	8
20	12344321	8
21	123443211	9	5
22	123443221	9
23	123443321	9
24	123444321	9
25	123454321	9

위의 표를 보면 same_cnt_times로 묶었을 때 행의 개수가 등차수열의 규칙을 이룬다는 것을 알 수 있습니다.

표에서 노란색으로 표시한 부분을 2로 나눈 값이 등차수열의 항의 순서(n)가 됩니다.

$$ 등차수열의 합 = {n(2a + (n - 1)d) \over 2}  $$

$$ a = 첫 항 $$

$$ d = 공차 $$

a = 2이고 d = 2이므로 등차수열의 합 = n(n + 1)

while문으로 입력받은 distance가 포함된 범위와 n을 구합니다.

distance에 매핑되는 cnt 는 2n-1이나 2n 중 하나가 됩니다.

1. diff(등차수열의 합과 distance의 차이)가 n보다 작을 때, cnt = 2n - 1
2. diff가 n보다 클 때, cnt = 2n

코드

import sys

t = int(sys.stdin.readline().rstrip())  # 테스트 횟수
for _ in range(t):
    x, y = map(int, sys.stdin.readline().rstrip().split())  # 현재 위치: x, 목표 위치: y
    cnt = 0  # 최소한의 공간이동 장치 작동 횟수
    distance = y - x  # 이동 거리
    n = 0  # 등차수열의 항
    while True:
        n += 1
        if distance <= (n * (n + 1)):
            diff = n * (n + 1) - distance
            if diff < n:
                cnt = 2 * n
            else:
                cnt = (2 * n) - 1
            break
    print(cnt)

 

 

 

Ref.

https://ooyoung.tistory.com/91

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

https://calcproject.tistory.com/448

[수학I] 20. 등차수열의 합 구하는 방법 (개념+공식+수학문제)