[백준] 1011번: Fly me to the Alpha Centauri

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

 

문제풀이

y지점에 도달하기 전 마지막 이동은 항상 1이어야 한다.

따라서 이동거리는 1 2 2 1, 1 2 3 2 1, 이런 식으로 점차 늘어났다가 줄어드는 형식이다.

 

 

찾은 규칙 1

경우의 수를 모두 나열해 보면 총 이동거리의 제곱근이 정수인 경우, 앞 뒤로 일정한 규칙이 보인다.

4의 제곱근은 2로, 정수이다.

따라서 이동거리는 위와 같이 대칭이 되는 구조이며

4를 포함하여 앞으로 두 경우는 장치 작동 횟수가 2 + 1 (제곱근 + (제곱근 - 1))

4를 포함하지 않고, 뒤로 두 경우는 장치 작동 횟수가 2 + 2 (제곱근 * 2) 이다.

 

처음에는 이렇게 복잡하게 생각하여 문제를 풀었는데,

문제를 다시 보니 단순히 더해서 풀 수 있는 문제였다.

 

 

찾은 규칙 2

양쪽 끝부터 순서대로 숫자를 더해서, 이동거리보다 같거나 큰, 대칭이 되는 수를 찾는다.

대칭이 되는 수의 이동거리가 홀수 개인 경우(빨간색), 장치 작동 횟수는 2*n - 1이며

대칭이 되는 수의 이동거리가 짝수 개인 경우(파란색), 장치 작동 횟수는 2*n이다.

 

예를 들어 y - x가 5인 경우,

① i = 1을 더한다. --- sum = 1

② sum이 5보다 크거나 같은지 비교한다.

③ i = 1을 한번 더 더한다. --- sum = 2

④ sum이 5보다 크거나 같은지 비교한다.

⑤ i를 증가시킨다.

⑥ i = 2를 더한다. --- sum = 4

⑦ sum이 5보다 크거나 같은지 비교한다.

⑧ i = 2를 한번 더 더한다. --- sum = 6

⑨ sum이 5보다 크거나 같은지 비교한다.

⑩ sum이 5보다 큰 6이므로 짝수 개인 경우에 해당, 장치 작동 횟수를 2*i로 계산한 후 출력한다.

 

※ 주의

여기서 주의할 점은, x와 y입력값 범위가 (0 ≤ x < y < 2³¹) 이라는 것이다.

입력값이 int범위를 넘지는 않지만, 계산하는 과정에서도 범위를 넘지 않는지 생각해봐야 한다.

sum과 result를 계산하는 과정에서 범위를 넘을 가능성이 있으므로, long long이나 unsigned int로 바꿔줘야 한다.

음수로 계산되는 경우가 없다고 생각해 unsigned int로 변경하였다.

 

 

소스코드

/*
 * 백준 1011번: Fly me to the Alpha Centauri
 */

#include <iostream>

using namespace std;

int main() {
	int T;
	cin >> T;

	while (T--) {
		int x, y;
		cin >> x >> y;

		// 이동거리
		int dist = y - x;
		unsigned int sum = 0;
		unsigned int result = 0;
		int i = 0;
		while (true) {
			sum += ++i;
			if (sum >= dist) {
				result = i * 2 - 1;
				break;
			}

			sum += i;
			if (sum >= dist) {
				result = i * 2;
				break;
			}
		}

		cout << result;
	}

	return 0;
}