[Python] 백준 / gold / 1011 : Fly me to the Alpha Centauri

문제 링크 : https://www.acmicpc.net/problem/1011

알고리즘 분류로 들어가서 푼게 아니라 그냥 골드로 들어가서 풀어봤던 문제. 유형을 모르는 상태로 풀어보는게 생각하는 연습이 더 잘 되는 것 같다. 근데 이건 풀고나서도 무슨 유형으로 분류해야할지 .. 굳이 분류하면 구현 + 그리디 인 것 같다.

그런데 요새 코딩테스트에 이런 유형이 잘 나오는 것 같다. 알고리즘 외우고 어떤 알고리즘으로 풀지 결정되면 그걸로 푸는 그런게 아니라, 문제 자체 이해 능력을 요구했던 것 같다.

이 문제의 핵심은 처음에도 스텝을 1 밟고, 마지막에도 스텝을 1 밟아야 한다는거였다. 근데 또 다음 스텝은 이전 스텝과 -1, 0, 1 차이가 나야되므로 마지막 스텝의 전 스텝은 1이나 2여야 한다는 거다.

이걸 고려해주기 위해서 시작 스텝 방향을 left 에 담고, 마지막 스텝 방향을 right 에 담아서 서로 -1, 1 씩 변화를 주면서 가운데서 만나도록 로직을 짜봤더니 정답처리 됐다.

파이썬 코드

import sys
T = int(sys.stdin.readline())

def program():
    x, y = map(int, sys.stdin.readline().split())

    left = 0
    right = 0

    gap = y-x
    turn = 'left'
    answer = 0

    while gap > 0:

        if turn == 'left':
            if gap >= left + 1:
                gap -= (left + 1)
                left += 1
            elif gap >= left:
                gap -= left
            else:
                gap -= (left - 1)
                left -= 1

            answer += 1
            turn = 'right'

        elif turn == 'right':
            if gap >= right + 1:
                gap -= (right + 1)
                right += 1
            elif gap >= right:
                gap -= right
            else:
                gap -= (right - 1)
                right -= 1

            answer += 1
            turn = 'left'

    print(answer)
    return

for _ in range(T):
    program()