[백준] 1011 Fly me to the Alpha Centauri (Python 파이썬)

문제 설명

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

1011번: Fly me to the Alpha Centauri

위 링크에서 주어진 설명처럼,

시작점과 끝점이 주어질 때 공간이동 장치의 작동횟수를 구하는 문제이다.

---

풀이 과정

먼저, 이 문제는 규칙을 찾아 해결하는 문제이다.

규칙을 찾는 과정이 굉장히 까다로웠는데, 규칙을 찾기 위해 직접 거리 1부터 직접 테이블을 작성해보았다.

먼저 거리가 제곱수일 때를 보면 (노란 배경색), 이동 단계에 새로운 숫자가 등장한다.

그 새로운 숫자는 제곱수의 제곱근이다.

 

그리고 그 수를 마지노선으로 다음 거리부터 작동 횟수가 +1 늘어난다.

하지만, 이 때만 작동횟수가 늘어나는 것은 아님을 알 수 있다.

그래서 다른 규칙을 찾기 위해 다음과 같은 방법을 이용해보았다.

 

표의 작동횟수 부분을 보면 작동횟수가 늘어나는데에는 다음과 같은 규칙이 있다.

위에서부터 작동횟수가 나타나는 규칙을 살펴보면

횟수1은 1번나타나고, 2도 1번 나타나지만 3은 2번, 4도 2번 나타난다.

[1-> 1번] [2-> 1번] [3-> 2번] [4-> 2번] [5-> 3번] [6-> 3번] [7-> 4번] [8-> 4번]...

이런 형식으로 나타남을 알 수 있는데,

[N-> M번] 에서 M번이 모두 2번씩 나타남을 알 수 있다.

 

이 규칙을 이용하면 거리에 따른 작동횟수를 구할 수 있다.

 

초기 이동거리는 0인 상태이며 작동 횟수도 0회이고 이동할 거리는 1로 고정이다.

 

그리고 위에서 설명한 것 처럼 작동횟수가 1, 2, 3, 3, 4, 4, 5, 5, 5, 6 ,6 ,6 ,7 ,7, 7, 7, 8, 8, 8, 8 ... 처럼

각 횟수가 나타나는 횟수가 2번이기 때문에

홀 수가 될 때 마다 각 작동횟수가 나타나는 횟수가 1씩 증가하므로

 

홀수일 때 마다 step(이동할 거리)를 1씩 높여준다.

(3번 나타나는 경우는 표의 행을 3칸 건너뛰고

2번 나타나는 경우는 표의 행을 2칸 건너뛰기 때문에)

 

설명이 조금 어려울 수 있는데, 이해가 잘 안된다면 위의 표처럼 직접 그려서 확인해보는 것을 추천한다.

t = int(input())

for i in range(t):
    x, y = map(int, input().split())
    dist = y - x
    step = 1        # 이동할 거리(초기는 1)
    cnt = 0         # 작동 횟수
    mydist = 0      # 초기 이동거리는 0

    while mydist < dist:
        cnt += 1
        mydist += step

        if cnt % 2 == 0:
            step += 1

    print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !