[백준] 1011 Fly me to the Alpha Centauri

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

문제의 조건에 맞게 각 거리별 이동에 필요한 최소 작동 횟수를 구하였습니다.

작동 횟수	이동 가능한 거리
1	1
2	2
3	3, 4
4	5, 6
5	7, 8, 9
6	10, 11, 12

 

위의 표와 같이 작동 횟수가 홀수가 될때마다 이동 가능한 거리의 개수가 1씩 증가하는 규칙이 발견되었습니다.

이에 따라 작동 횟수, 이동 가능한 거리의 개수, 마지막 이동 가능한 거리를 변수로 관리하여 탐색하였습니다.

2) 알고리즘

• 수학

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

T = int(sys.stdin.readline())

for _ in range(T):
    # 입력
    x, y = map(int, sys.stdin.readline().split())

    # 이동해야 할 거리
    distance = y - x
    # 작동 횟수, 작동 횟수당 이동 가능 거리 개수, 마지막 이동 거리
    ans, g, last_dist = 0, 0, 0

    while True:
        # 작동 횟수 증가
        ans += 1

        # 작동 횟수가 홀수라면 이동 가능한 거리 개수 1 증가
        if ans % 2:
            g += 1

        # 마지막 이동 가능 거리 변경
        last_dist += g

        # 현재 작동 횟수로 이동이 가능하면 종료
        if last_dist >= distance:
            break

    print(ans)

---

🔗 문제 링크

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

1011번: Fly me to the Alpha Centauri

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다