[BOJ][Python]1011 풀이

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

1011번: Fly me to the Alpha Centauri

import sys
ssr = sys.stdin.readline

t = int(ssr())
for _ in range(t):
    x, y = map(int, ssr().split())
    dist = y-x
    rep = dist**(1/2)
    if rep <= int(f'{rep:.0f}'):
        print(int(f'{rep:.0f}')*2-1)
    else:
        print(int(f'{rep:.0f}')*2)

예전에 풀었던 문제인데 재채점으로 틀렸다고 되어있길래 다시 풀어봤습니다. 원래 코드랑 크게 바뀐 부분은 없는데 가독성이랑 혹시 모를 round에러(정확하게는 파이썬의 round가 오사오입을 따르기 때문에 답이 틀리는 경우가 있기 때문입니다)를 잡기 위해서 f-string법을 이용해서 포맷팅을 진행했습니다.

 

사실 해당 문제는 코드는 간단한 것에 비해서 생각을 끌어내는데는 오래걸렸던 것으로 기억합니다. 문제가 어려운 건 아닌데 막 수의 규칙성을 찾다보면 머리가 복잡해져서 이게 헷갈리고 저게 헷갈리는 그런 상태가 지속되다보니 아까 어떻게 생각했는지 기억 안나는 그런 거 있잖아요. 딱 그런 문제입니다.

 

이 문제에서 가장 중요한 조건은 n번째 이동은 n-1번째 이동보다 1작거나 같거나 1커야 한다 입니다. 굳이 강조하는 이유는 y에 도착하는 경우는 무조건 이동거리가 1이어야 한다라는 조건을 보고 자기도 모르게 아 그냥 1만 빼면 되겠구나 하고 생각하는 분을 몇 분 봬서 그렇습니다. 즉 y에 도착하기 전에는 마지막 이동거리를 1로 할 수 있도록 만들어놔야 한다는 뜻이죠. 직전 이동거리를 2나 1로 해야한다는 뜻입니다. 최소 횟수로 이동하기 위해서 열심히 늘려놨던 이동거리를 줄여도 1씩밖에 못 줄이니 미리 준비를 해야겠죠.

 

그래서 저는 이동에 대한 경우를 하나씩 손으로 써봤던 것 같습니다. 예전에 풀었던 문제라 기록이 안남아있어서 오늘 다시 손으로 써보긴 했습니다만, 간단하게 써보면,

1 : 1

2 : 1 1

3 : 1 1 1

4 : 1 2 1

5 : 1 2 1 1

6 : 1 2 2 1

7 : 1 2 2 1 1

8 : 1 2 2 2 1

9 : 1 2 3 2 1

뭐 이런식으로 이동하는 패턴이 나오게 됩니다. 그래서 이걸 20 정도 까지 해보면 패턴을 찾을 수 있는데요.

이동 횟수가 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10... 이렇게 1씩 올라가면서 반복은 2번에 1회씩 올라가는 그런 패턴을 찾을 수 있습니다. 사실 저도 손으로 했던 것이다 보니 뭐라고 설명을 잘 드리기가 어려운데요.

 

그래서 이 내용을 정리를 해보면 n번 반복은 거리의 제곱근을 구했을 때 나오는 n.xxxx가 있을 때 n-0.5 ~ n는 n*2-1회의 이동횟수를 갖고 n~n+0.5까지는 n*2회의 이동 횟수를 갖습니다. 풀이를 적다보니 이게 왜 이런 규칙을 갖는지 저도 궁금해졌는데 추가적으로 공부를 해서 수정을 하도록 하겠습니다.

 

수정// 파이썬에서 진행하는 반올림은 내부적으로 오사오입의 규칙을 따르기 때문에 round나 문자열 포맷팅이나 다 오사오입을 따릅니다. 기존에 적혀있었던 내용은 잘못된 내용이며 해당 내용으로 인해 혼동을 겪으셨을 분들께 사과드립니다. 반올림을 우리가 원하는 방향으로 진행하도록 하기 위해서 결과에 영향을 주지 않는 선에서 작은 숫자를 더해주는 테크닉을 사용할 수 있습니다.

ex)

round(2.5)

>> 2

round(2.5 + 0.000000001)

>> 3