백준 알고리즘 1011번 - Fly me to the Alpha Centauri (C 언어)

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					4회
6	1	2	2	1					4회
7	1	2	2	1	1				5회
8	1	2	2	2	1				5회
9	1	2	3	2	1				5회
10	1	2	3	2	1	1			6회
11	1	2	3	2	2	1			6회
12	1	2	3	3	2	1			6회
13	1	2	3	3	2	1	1		7회
14	1	2	3	3	2	2	1		7회
15	1	2	3	3	3	2	1		7회
16	1	2	3	4	3	2	1		7회

 

이런식으로 25까지 쭉 써서 규칙을 찾아보았다.

---

 

이동 해야하는 거리가 N광년일 때, 한 번에 최대로 이동할 수 있는 거리는 (int)√N 광년이다.

 

(int)√N을 X라고 하자.

 

ex) 이동 해야하는 거리가 26광년이면 √26 = 5.xxx이므로 X = 5

 

---

 

한 번에 최대로 이동할 수 있는 거리가 X 광년일 때

최소 이동 횟수는 2X - 1번이며

최대 이동 횟수는 2X + 1번이다.

 

2X + 2번 이동하려고 할 때, X값이 1씩 증가한다.

 

ex) 최대 이동 거리가 4 광년이면

 

1 2 3 4 3 2 1로 이동해야 한다.

 

이 때 최소 이동 횟수는 7회이다 (4 x 2 - 1)

 

이때 최대 이동 거리를 변경하지 않고 최대로 이동할 수 있는 방법은

 

1 2 3 4 4 4 3 2 1이다. (24광년 이동)

 

---

 

위 규칙을 정리하면

 

N : 이동해야하는 거리

X : 한 번에 최대로 이동할 수 있는 거리

 

case 1 ) N - (X * X) = 0일 때

 

이동 횟수 : 2X - 1

 

case 2 ) n - (X * X) ≤ X 일 때

 

이동 횟수 : 2X

 

case 3 ) 나머지 경우

 

이동 횟수 : 2X + 1

 

수학적인 증명은 잘 모르겠고.. 끄적끄적 하다보니 규칙을 찾았다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
	int t, i, start, end, distance, root, square, count = 0;

	scanf("%d", &t);

	for (i = 0; i < t; i++)
	{
		scanf("%d %d", &start, &end);
		distance = end - start;
		root = (int)sqrt(distance);
		square = root * root;
		count = 2 * root - 1;

		if (distance - square == 0)
			;
		else if (distance - square <= root)
			count++;
		else
			count += 2;

		printf("%d\n", count);
	}

	return 0;
}