[기본수학] 1011번 Fly me to the Alpha Centauri

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 1시간 + a

1. 문제 설명

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

1011번: Fly me to the Alpha Centauri

- 특정한 이동 장치를 이용해서 이동하는 우주선이 있다. 해당 우주선이 x에서 y로 이동할 때 이동장치를 최소로 이용하는 방법은 무엇인가?

2. 접근 방식

- 처음에는 다양한 예외 케이스를 고려해서 반복문을 이용해 수를 증가시키려고 했는데, 시간초과가 발생했다.

- 결국 특정한 규칙을 이용해야하는 문제였다. 

x와 y의 차를 기준으로 볼 때, 아래와 같은 규칙을 가진다.

x,y의 차가 1일 때 거리는 1
x,y의 차가 2일 때 거리는 2
x,y의 차가 4일 때 거리는 3
x,y의 차가 6일 때 거리는 4
x,y의 차가 9일 때 거리는 5
x,y의 차가 12일 때 거리는 6
x,y의 차가 16일 때 거리는 7
x,y의 차가 20일 떄 거리는 8

따라서 x, y 의 차가 1 2 2 3 3 4 4 ... 이런 식으로 차이가 나게 됨으로 이를 코드로 구현하면  문제를 해결할 수 있다.

 

3. 코드

- 초기 실수한 코드 ( 반복문 ) [틀린 코드]

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    x, y = map(int, input().split())
    length_xy = y-x
    case = [0, 1, 2] # 부터 시작
    count = 1
    dist = 1
    if length_xy == 1:
        print(count)
        continue
    if length_xy > 3:
        while True:
            dist += case[2]
            case = [case[2]-1, case[2], case[2]+1]
            count += 1
            if dist >= length_xy//2:
                break
    while True:
        if length_xy == dist:
            print(count)
            break
        if (length_xy-dist) <= 2:
            dist += 1
        else:
            dist += case[0]
            case = [case[0]-1, case[0], case[0]+1]
        count += 1

- 해답 코드 (규칙을 구현)

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

    count = 0
    distance = 0 
    a = 0.5 # 0.5로 둔 이유는 count가 2번증가할 때 1이 증가해야 하기 때문
    
    while length_xy > distance:
        a += 0.5
        distance += int(a)
        count += 1
    print(count)

4. 코멘트

- 1시간 넘게 고민하다가 결국 다른 분의 코드를 본 문제였다. 해당 문제의 경우 초기 방향을 잘못 정한 것도 같기는 하다.

- 알고리즘을 잘 짜기 위해서는 규칙을 파악할 수 있어야 하는데 규칙을 찾아내기까지가 어려운 것 같다. (물론 당연한 얘기일 지도)

- 규칙을 찾기 위해 문제를 먼저 사전에 제대로 정리해야할 필요가 있어보인다.