[백준 1011] Fly me to the Alpha Centauri - python (solved.ac - 골드 5)

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

1011번: Fly me to the Alpha Centauri

풀이

문제를 보았을때 알수있는 힌트

입력의 2^31으로 되어있기 때문에 반복문을 쓰는 건 아닌듯하다.

그러면 패턴을 찾아서 풀어야 하는 느낌이 들었다.

이동거리	순서	최소 횟수	반복 횟수
1	1	1	1
2	11	2	1
3	111	3	2
4	121	3
5	1121	4	2
6	1221	4
7	11221	5	3
8	12221	5
9	12321	5
10	122221	6	3
11	122321	6
12	123321	6
13	1223221	7	4
14	1233221	7
15	1233321	7
16	1234321	7
17	12343211	8	4
18	12343221	8
19	12343321	8
20	12344321	8

이동 거리와 최소 횟수를 적어보면 패턴이 보이기 시작한다.

또한 2번씩 해서 반복횟수가 증가하는 것을 볼수있다.

이를 활용하면 문제를 빠르게 해결할수있을듯하다.

 

예를 들어 11의 최소 횟수를 찾고 싶다면 반복 횟수가 어떻게 되는지 먼저 찾는다.

반복 횟수가 될수있는 최대 이동거리를 찾으면 된다. 11이기때문에 3의 반복횟수를 찾아야하고 이를 반복문을 통해서 찾는다. n*(n+1)를 하면 3일때 12로 최대 이동거리와 일치하는 것을 알 수 있다.

이제 n의 값이 3인 것을 알았으니 최소 횟수를 찾으면 된다. 

3일때 최소 횟수는 5와6의 숫자가 나와야한다. 이를 식으로 찾으면 (n*2)-1,n*2 이렇게 된다.

이 두개중 하나를 찾아야하는데 이동거리 9를 기준으로 같거나 작으면 (n*2)-1, 큰 경우에는 n*2 이된다.

이때 9 역시 식으로 보면 n**2가 되는 것을 알수있다.

 

이것을 식으로 작성하면 

import sys

input = sys.stdin.readline

t= int(input())

for _ in range(t):
    x,y= list(map(int,input().split()))

    distance = y-x
    n=0

    while True:
        if distance<=n*(n+1):
            break
        n+=1
    if distance<=n**2:
        print(n*2-1)
    else:
        print(n*2)

이렇게 된다.

나역시 처음에 패턴을 못찾아서 다른 사람들의 힌트를 보고 찾을수있었다.. ㅠ

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1011.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리