[백준] 1011번 Fly me to the Alpha Centaur _ Python

[초기 접근 방법]

1) 문제 조건 위배 (x)

def solve(move):
    if move <= 1:
        return move

    k = 1
    go = 1

    while True:
        k += 1
        go += k

        # 이동거리 move를 만족할 시 stop
        if go >= move:
            break

    return k

 

- 도착 직전 이동거리가 1광년이라는 것을 고려하지 않았다.

 

 

 

2) dp (x)

dp[i] : i 위치까지 가는데, 장치 작동 횟수의 최솟값
    점화식
    k : 직전에 이동한 거리 +- 1
    dp[i] = dp[i-k] + 1
    dp[i+k] = min(dp[i+k], dp[i] + 1)

 

- 경우의 수가 매우 많아진다.

 

 

 

[생각]

- 수학적인 규칙을 찾는 문제이다.

- 빠른 유형 파악과, 노트에 끄적이면서 수학적인 규칙을 빨리 찾는 훈련이 필요할 듯하다.

 

 

 

[코드]

# 풀이 시간 : 35분 + 40분(dp) + 30분
# 시간복잡도 : O(1)
# 공간복잡도 : O(1)
# 참고 : https://kiffblog.tistory.com/181
#       https://st-lab.tistory.com/79

# 1
# ---------
# 1, 1
# 1, 1, 1
# 1, 2, 1 = *4 (기구 3번 사용 : 홀수 경계값)
# ---------
# 1, 2, 1, 1 (4번 사용)
# 1, 2, 2, 1 → 6 (4번 사용 : 짝수 경계값)

# 1, 2, 2, 1, 1 (5번 사용)
# 1, 2, 2, 2, 1 (5번 사용) n = 2
# 1, 2, 3, 2, 1 = *9 (5번 사용 : 홀수 경계값) n = 3
# ---------
# 1, 2, 3, 2, 1, 1

# 홀수(2n-1)번 이동할 때, 최대이동거리는 "n^2" 이다.
    # n(n+1)/2 * 2 - n = n^2
# 짝수(2n)번 이동할 때, 최대이동거리는 "n^2+n" 이다.
    # n(n+1)/2 * 2 = n^2 + n


import math
def solve(move):
    n = int(math.sqrt(move))

	# 이동횟수 move가, 최대이동거리 n^2일 때
    ## 기구 사용 횟수는 2n-1이 된다.
    if move == (n ** 2):
        result = 2 * n - 1

    # 홀수번 경계값 초과, 짝수번 경계값 이하일 때
    ## 기구 사용 횟수는 2n이 된다.
    elif n ** 2 < move <= n * (n + 1):
        result = 2 * n

    # 이 외의 경우, 즉 홀수 경계값 move가 제곱수가 되기 직전
    ## 기구 사용 횟수는 2n+1이 된다.
    else:
        result = 2 * n + 1

    return result



T = int(input())
for _ in range(T):
    x, y = map(int, input().split())

    move = y-x # 총 이동 거리

    print(solve(move))

 

 

 

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

1011번: Fly me to the Alpha Centauri