1011번(Fly me to the Alpha Centuari) 파이썬(Python) 풀이 공유

들어가며

약 2개월 이라는 기간을 두고 총 두 번 풀었던 문제인데, 수열을 다룰 줄 안다면 훨씬 쉽게 해결 가능한 문제이다.

문제 풀이

문제에서 최종적으로 요구하는 사항을 정리해보면, x에서 y로 이동하기 위한 공간이동 장치의 최소 작동 횟수를 찾는 것이다. 단, 아래의 조건을 만족시켜야 하는데, 이 중에서 세 번째 조건이 문제의 핵심 포인트라고 할 수 있다.

• 공간 이동 장치를 처음 작동시킬 때 이동 가능한 범위는 -1, 0, 1 광년이다.
• 공간 이동 장치로 이동한 거리를 k 광년이라고 할 때, 다음에 이동할 수 있는 거리의 범위는 k-1, k, k+1 광년이다.
• y에는 반드시 1 광년 만큼만 이동해서 도착해야 한다.

만약, X가 1, y가 6으로 주어질 때로 가정해보자. 먼저, x에서 y로 이동하기 위한 총 이동거리(y - x)는 5광년이다. 또한, 공간이동 장치를 처음 작동시킬 때 이동 가능한 범위는 -1, 0, 1인데, 문제에서는 x에서 y로의 이동 즉, 양의 방향으로 이동해야 하므로 이동 가능한 범위는 1 광년만 유효하게 된다. 따라서, 처음 장치를 작동시킬 때에는 1 광년만큼 이동하고, 다음 공간이동 장치의 범위는 0, 1, 2가 된다.

이동한 거리	다음 이동 가능 범위	남은 이동 거리
1 광년	0, 1, 2	4 광년

공간이동 장치를 최소한으로 작동시켜야 하므로 두 번째 이동 거리는 2광년으로 하면, 다음 공간이동 장치의 범위는 1, 2, 3이 된다.

이동한 거리	다음 이동 가능 범위	남은 이동 거리
2 광년	1, 2, 3	2 광년

이제 남은 이동 거리가 2 광년 남았다. 그렇다면 이동 가능 범위 중 2 광년으로 이동하면 될까? 절대 그렇지 않다.그 이유는 위에서 주어진 조건 중 세 번째 조건에 따라 y에 도착하기 전에는 반드시 1 광년 만큼만 이동해서 도착해야 하므로 1 광년 만큼만 이동해야 하기 때문이다. 즉, 1 광년 만큼 이동하여 다음 장치의 이동 가능 범위를 0, 1, 2로 만들고, 마지막 이동 시점에 1 광년 만큼 이동하면 세 번째 조건을 충족시킬 수 있다.

이동한 거리	다음 이동 가능 범위	남은 이동 거리
1 광년	0, 1, 2	1 광년
1 광년	0, 1, 2	0 광년 (도착)

문제의 내용을 이해했다면 x, y 값으로만 작동 횟수를 알아내는 규칙성을 찾아야 한다. 위에서 살펴본 내용을 바탕으로 아래와 같이 테스트 케이스를 작성한 끝에 몇 가지 규칙을 찾아내었다.

총 이동 거리(y - x)	이동한 내역	작동 횟수
1	1	1
2	1, 1	2
3	1, 1, 1	3
4	1, 2, 1	3
5	1, 2, 1, 1	4
6	1, 2, 2, 1	4
7	1, 2, 2, 1, 1	5
8	1, 2, 2, 2, 1	5
9	1, 2, 3, 2, 1	5
10	1, 2, 3, 2, 1, 1	6
11	1, 2, 3, 2, 2, 1	6
12	1, 2, 3, 3, 2, 1	6

위 표에서 작동 횟수가 같은 총 이동 거리의 최대값은 1, 2, 4, 6, 9, 12 ...로 나타낼 수 있다. 이 수열의 증가분은 1, 2, 2, 3, 3, 4 ...로 나타낼 수 있다. 즉, 작동 횟수가 같은 총 이동 거리의 최대값을 수열의 값만큼 증가시켜서 y - x가 총 이동 거리의 최대값보다 작거나 같은 시점을 찾으면 된다. 이를 코드로 나타내면 다음과 같다.

def value():
    x, y = map(int, input().split())
    return y - x


for _ in range(int(input())):
    distance = value()            # 총 이동 거리
    maximum = 0                    # 작동 횟수 별 총 이동 거리의 최대값
    increase = 1                # 증가분
    add = False                    # 증가 여부
    count = 1                    # 작동 횟수

    while True:
        maximum += increase        # 최대값을 증가분만큼 증가

        if add:
            increase += 1        # 증가분 1 증가 ex) [1, 2, 2, 3, 3...]

        add = not add            # 증가 여부 역전화

        if distance <= maximum:
            break                # 총 이동 거리가 작동 횟수 별 최대값에 포함되는 경우

        count += 1                # 작동 횟수 1 증가

    print(count)

마치며

알고리즘 고수들은 피식하고 웃을 수 있지만, 나 자신이 확실히 성장했다고 느껴지는 문제라고 생각된다. 그 이유는 2개월 전에 이 문제를 풀었을 때와 지금의 접근 방식이 아예 다르기 때문이다. 기억이 가물가물할 만큼 몇 시간을 문제의 늪에 빠져서 허우적대다가 결국은 풀었었지만 명확하게 설명은 하지 못할 정도였기 때문이다. 달리 말하자면, 찍어 맞춘 문제였다. 시간이 지나 이 문제를 다시 보니 보이지 않던 명확한 규칙이 보이고, 그 규칙을 어떻게 코드로 옮겨야 할 지 이제는 조금 알 것 같다는 느낌에 자신있게 문제를 풀었다.