백준 1011번 Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri

문제 접근 🤔

• 단순하게 (y-x)-1로 하고, 0이면 -1을 안하는 방식으로 갈려고 했다.
• -1, 0, 1 → 0, 1, 2 → 1, 2, 3.. 이여서 안됐다.
  • 16% 테스트 케이스에서 틀렸다고 뜬다.

놓쳤던 부분 😅

• 문제 이해를 제대로 안하고 코드 부터 짠거 같다.
• 값을 나열하면 규칙이 있는데 제곱근을 사용하면 규칙을 풀 수 있다.

코드 😁

첫 번째 코드 - 실패

import sys

readline = sys.stdin.readline

n = int(readline())

for _ in range(n):
    x, y = map(int, readline().split())
    if x <= 0:
        print(y)
        continue

    print((y-x)-1)

두 번째 코드 - 티스토리

import math
import sys

readline = sys.stdin.readline

# N 입력
n = int(readline())

# N만큼 반복
for _ in range(n):
    x, y = map(int, readline().split())

    # 남은거리
    distance = y - x

    # 거리에 따라 이동한 횟수
    cnt = 0

    # 최대거리 제곱근
    distance_max = int(math.sqrt(distance))

    # 최대거리와 남은거리 마다 계산이 다르다
    # 이동 패턴은 1,2,3..N..,3,2,1 형식
    # 해당 패턴은 거리가 정확히 n^2일 때 적용이 됨

    # 거리가 정수의 제곱인 경우
    # 1부터 n까지 증가하고 다시 n-1까지 감소
    # 왜 제곱근 * 2 - 1 인가?
        # 증가할땐 n
        # 감소할땐 n - 1
        # 총 이동 횟수가 n + (n - 1) = 2n - 1
    if distance_max == math.sqrt(distance):
        cnt = distance_max * 2 - 1

    # 남은거리가 최대거리의 제곱 + 최대거리보다 같거나 작으면
    # 거리에 따라 이동한 횟수: 제곱
    # 왜 제곱근을 제곱하는가?
        # 총 이동 횟수 n + (n - 1) = 2n - 1인데
        # 최대 이동 단계인 n을 한번 더 이동 해야하니깐 2n - 1 + 1 = 2n이 돼서
    elif distance <= distance_max * distance_max + distance_max:
        cnt = distance_max * 2

    # 그 외
    # 거리에 따라 이동한 횟수: 제곱 + 1
    # 왜 제곱근에 + 1인가?
        # 총 이동 횟수 증가하는 n, 감소하는 n을 합하면 n + n = 2n이 됨
        # 최대 이동 단계에서 초과 하기에 한번 더 이동하여 2n + 1
    else:
        cnt = distance_max * 2 + 1

    # 결과 출력
    print(cnt)