1011번: Fly me to the Alpha Centauri (C언어)

# 문제

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

1011번: Fly me to the Alpha Centauri

---

# 풀이

## 변수 설명

• T: 테스트케이스 횟수
• x: 시작 위치
• y: 끝 위치
• move_count: 이동 횟수
• remain_space: 남은 거리
• move : 이동 거리

## 문제 해석

• 이동 가능한 거리 -> 그 중에 선택해서 이동 -> 이동 횟수 증가

예제 입력 1

0 to 3
이동 가능한 거리	이동	현재 위치	이동 횟수
-1, 0, 1	1	1	1
0, 1, 2	1	2	2
0, 1, 2	1	3	3

1 to 5
이동 가능한 거리	이동	현재 위치	이동 횟수
-1, 0, 1	1	2	1
0, 1, 2	2	4	2
1, 2, 3	1	5	3

 

45 to 50
이동 가능한 거리	이동	현재 위치	이동 횟수
-1, 0, 1	1	46	1
0, 1, 2	2	48	2
1, 2, 3	1	49	3
0, 1, 2	1	50	4

## 규칙

• 1부터 시작해서 1로 끝난다.
• 이동거리는 1씩 증가하고 1씩 감소한다.
• 어떤 수가 나오더라도 12345...4321 혹은 12345...43211의 형태가 나온다. 끝에 1이 더 붙을 수 있다.
• 양쪽의 숫자가 1, 2, 3, ...의 형태로 1씩 증가한다.
• 1231, 12341처럼 1이상 차이가 나는 거리를 한 번에 이동할 수 없다.

## 방법

• move는 1부터 시작해서 1씩 증가가 된다.
• 양쪽의 거리가 같으므로 이동해야하는 거리(x - y)에서 move * 2만큼 빼주고 남은 거리(remain_space)로 체크를 한다.
• 양쪽의 거리를 한 번에 이동 시켰으므로 이동 횟수(move_count)는 2를증가시킨다.
• 남은 거리가 0보다 클 경우, 반복해서 move를 1씩 증가시켜서 빼준다. 0보다 작거나 같으면 출력한다.
• 남은 거리가 이동거리보다 적을 경우 이동 횟수(move_count)에서 1을 빼준다.
  (양쪽의 이동을 한번에 하는데 남은 거리가 이동 거리보다 작으면 두 칸을 움직일 필요가 없이 한 칸만 움직이면 되기 때문)
• 남은 거리가 move * (-1)보다 같다면 이동 횟수에서 -1을 해준다.
  (예를 들어, move는 2인데 이동 후, 남은 거리가 -2일 경우, 한 번 덜 움직여도 됐기 때문이다.)

## 예를 들어

0 to 10 (0부터 10까지 최소한으로 움직여야한다.)

move	remain_space	move_count
-	10	0
1	8	2
2	4	4
3	-2	6

1, 2, 3, 3, 2, 1로 이동했다고 표현할 수 있다.

잘 보면 move_count는 6으로 맞지만 움직인 거리는 1 + 2 + 3 + 3 + 2 + 1 = 12이다. 

10만큼 이동해야하는데 14만큼 이동한 것이다. 그럼 이 방법은 잘못된 것일까? 아니다.

 

실제로 최소한으로 움직이려면 이동해야하는 값은 1, 2, 2, 2, 2, 1 혹은 1, 2, 3, 2, 1, 1이다.

10을 넘어간다고 하더라도 실제로는 그 자리에 다른 숫자가 들어갈 뿐, 이동 횟수는 같다.

단, 두 번 움직이 않고 끝낼 수 있는 경우는 move_count에서 -1을 해줘야한다.

 

+) 1, 2, 3 다음 4는 올 수 없다.

왜냐하면 4를 움직이려면 양쪽의 3을 이동하고도 남은 거리가 있어야한다.

4가 오게되면 다음에 3이 와야하는데 1이 되기도 전에 10을 넘어버린다. (규칙을 보면 마지막에 1을 이동해서 10이 되어야한다.)

 

 

---

# 소스 코드

#include <stdio.h>

int	main(void)
{
	int	T;	// 테스트 케이스 횟수
	int	x, y;	// x: 시작 위치, y: 끝 위치. (0 <= x < y < 2^31)
	int	move_count;	// 이동 횟수
	int	remain_space;	// 남은 거리
	int	move;	// 이동 거리

	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &x, &y);
		move_count = 0;
		remain_space = y - x;
		move = 1;
		while (remain_space > 0)
		{
			if (remain_space < move)
				move_count -= 1;
			remain_space -= (move * 2);
			move_count += 2;
			if (remain_space <= 0)
			{
				if (remain_space == -(move))
					move_count -= 1;
				break ;
			}
			move++;
		}
		printf("%d\n", move_count);
	}
	return (0);
}