백준 1011번 Fly me to the Alpha Centauri [파이썬]

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

이 문제를 풀기 위해서 보통은 거리만큼 스텝의 횟수를 적어서 패턴을 찾으려고 한다.

거리	이동 패턴	횟수
1	1	1
2	1 1	2
3	1 1 1	3
4	1 2 1	3
5	1 2 1 1,  1 1 2 1	4
6	1 2 2 1	4
....	....	.....

이렇게 패턴 찾아서 코드를 짠다. 하지만 이번 알고리즘 주차에서 만난 분의 풀이는 다음과 같았다.

import sys
input = sys.stdin.readline
T = int(input())   # test case 횟수

# 양끝에서 동시에 출발, 서로 만나거나 겹칠 때까지 동작. 
# 그때까지 양쪽에서부터 각각 이동한 횟수를 더한다. 
for i in range(T):
    x, y = map(int, input().split())
    start = 0; end = y-x           # 시작점과 끝점의 위치. 위치가 변하면서 갱신된다
    start_cnt = 0; end_cnt = 0   # 시작점과 끝점에서 이동하는 횟수

    k = 1   # 첫 이동거리
    while start < end:
        # 시작점과 끝점에서부터 이동하는 동작
        start += k
        start_cnt += 1
        # 시작점에서 이동한 것이 끝점에서 이동한 것과 
        # 만나거나 넘어갈 때까지 동작을 시행한다.
        if start >= end:    # if문이 여기 있어야 하는 이유는
            break           # 거리차가 1인 경우는 바로 끝내버리기 위해서다.
                            # if 문이 끝점 이동 동작 다음에 오면 거리차가 1이면 이동 동작이 겹쳐서 답이 2가 된다.
        end -= k
        end_cnt += 1
        
        if start >= end:
            break
        
        k += 1        # 다음번에는 이동폭이 1만큼 늘어난다. ex) 1 -> 2 -> 3 ... 이렇게 해야 최소 횟수로 이동한다. 
    print(start_cnt + end_cnt)
    

어차피 문제가 원하는 답은 총 이동 횟수이다. 그러면 출발점에서만 출발했을때 횟수와, 양쪽에서 출발해서 중간에서 만날 때 걸리는 횟수를 각각 더해 나온 총 횟수는 같다. 이렇게 군더더기 정보와 고정관념(한쪽에서만 출발한다)를 덜어내고 나니 코드가 간결해졌다. 

이 코드를 이해했을때 느낌은 그야말로 '가슴이 웅장했졌다'. 이 코드야말로 '겉으로는 보이지만 문제풀이에는 쓸모없는 정보를 덜어내고 문제 풀이의 본질만 꿰뚫은 무시'의 힘을 보여주는 사례다. 

(깨봉수학 대표인 조봉한 박사님의 수학 풀이법을 보고 깊은 감명을 받고 그분의 수학적 사고 철학인 무시-변화-관계를 나도 익히려고 하는데, 이 문제 풀이는 조봉한 박사님이 설명한 무시의 정의에 가장 어울리는 풀이다)