[백준 1011] Fly me to the Alpha Centauri 파이썬 python

문제

나의 풀이

소스코드

t = int(input())

for _ in range(t):
    x, y = map(int, input().split())
    
    distance = y - x # y와 x사이의 거리
    tmp = 0 # 이동 거리
    cnt = 0 # 공간 장치 이동 횟수
    moving = 0 # 반복 횟수

    while tmp < distance:
        cnt += 1
        if cnt % 2 != 0:
            moving += 1
        tmp += moving
    print(cnt)

해설

백준 단계별 풀어보기 하는 중 안풀려서 며칠 고민했던 문제다.

수학 유형은 직접 나열해보면서 규칙성을 파악해야한다.

특히, 문제에서 종료조건을 제대로 설정안해서 처음에 비효율적이고, 시간 초과가 나오는 코드를 만들었다.

 

1. 공간 장치 이동 횟수는 (공간 장치 이동 횟수 % 2) 만큼 반복되고,

2. 공간 장치 이동 횟수가 홀수가 될 때 마다 반복되는 횟수가 증가하는

 

규칙이 있음을 확인할 수 있다.

1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10 ..이런식으로..

 

 

1) 변수 정의

이동한 거리를 세는 임시 변수 tmp, 공간 장치 이동 횟수인 cnt, 공간 장치 이동 횟수가 반복되는 수를 moving으로 정의했다.

distance = y - x # y와 x사이의 거리
tmp = 0 # 이동 거리
cnt = 0 # 공간 장치 이동 횟수
moving = 0 # 반복 횟수

 

 

2) 이동 하기

공간 장치 이동 횟수가 홀수일 때마다 반복 횟수를 증가 시키고,

공간 장치 이동 횟수를 (공간 장치 이동 횟수 % 2) 만큼 반복시킨다.

cnt += 1
if cnt % 2 != 0:
    moving += 1
tmp += moving

 

 

3) 종료 조건

tmp < distance

이동한 거리가 distance보다 커지면 cnt(공간 장치 인동 횟수) 값을 갱신하는 것을 중단한다.