새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 1011 Fly me to the Alpha Centauri

by 언호 2022. 8. 21.

📖 문제


🧑🏻‍💻 풀이 과정

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

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 17837 새로운 게임 2  (0) 2022.08.25
[백준] 1525 퍼즐  (0) 2022.08.24
[백준] 2437 저울  (0) 2022.08.19
[백준] 4195 친구 네트워크  (0) 2022.08.18
[백준] 1944 복제 로봇  (0) 2022.08.17

댓글