728x90
문제는 다음과 같다.
문제 이해하는데 애 좀 썼다.
중요한 것은 바로 k
k는 0부터 시작하여 k-1, k, k+1
0에서 시작하면 -1, 0, 1 만큼 움직일 수 있다.
처음 시작할때 왼쪽으로 갈 필요는 없으므로 무조건 1로 움직인다.
(그림에서 x가 왼쪽, y가 오른쪽. 우리는 x에서 y로 간다.)
k는 1로 변하여
0, 1, 2 만큼 갈 수 있다.
최소한으로 움직일 것이기 때문에 2만큼 가서,
k=3으로 변하고,
2,3,4으로 움직일 수 있다.
하지만, 여기서 y지점 바로 전에는 1광년만 움직일수 있다.
입력 예시를 보자.
첫번째 X = 0 , Y = 3이며 현재 이동한 횟수 (cnt) 0
처음에 k=0 이므로 -1, 0 , 1
하지만 앞서 설명했다시피 왼쪽으로 갈 필요는 없다. 1로 이동
k = 1 , cnt = 1
0, 1, 2 광년만큼 이동할 수 있다.
최소한으로 걸어야하기 때문에 2광년을 가야하지만,
2광년을 가면 현재 도착지점인 3이다.
도착지점 바로 전에는 1광년만 갈 수 있다.
1로 선택하여 이동
k = 2, cnt = 2
0,1,2 에서 도착지점인 y지점만큼 1광년이 남았다.
1광년을 이동하고 이동횟수를 1더해준다.
총 이동횟수 cnt = 3이 출력된다.
풀이 코드는 다음과 같다.
n = int(input())
for i in range(n):
X, Y = map(int, input().split())
a = Y - X # 이동해야할 거리 (최대 횟수, 1만큼씩 이동시)
cnt = 0 # 이동 횟수 (출력 값)
k = 1 # k는 k-1, k , k+1로 1만큼 차이나므로 1로 변수설정
m_p = 0 #총이동한거리
while m_p < a: #총 이동 거리가 이동해야할 거리보다 짧아야하므로
cnt +=1 # 이동횟수 1 증가
m_p += k # x에서 y까지에서 총 k만큼 이동하므로 처음 이동거리에서 더해줌
if cnt % 2 == 0: # cnt가 2의 배수이면
k += 1 # k는 1증가
print(cnt)
728x90