c언어 1011번 Fly me to the Alpha Centauri (백준)

#include <stdio.h>
//unsigned long long int 범위 : 0 ~ 1.8446744e+19
//문제에서 입력 받은 수의 범위 : 0~4294967295
//즉 오버플로우가 일어나지 않는다
int main(void)
{
	int t;
	scanf("%d", &t); //몇 번?
	while(t>0)
	{
		unsigned long long int n, m;
		scanf("%lld%lld", &n, &m); //입력 받음
		unsigned long long int gap = m-n;
		
		unsigned long long int i;
		for(i = 1; i>0; )
		{
			unsigned long long int key_1 = i*i; 
			unsigned long long int key_2 = (i+1)*(i+1);
			unsigned long long int key_3 = (key_2+key_1+1) / 2;
			if(key_1 <= gap && gap <= key_2) //두 제곱수 사이의 수라면
			{
				if(key_1 == gap) {//작은 제곱수와 gap이 같을 때
					printf("%lld\n", 2*i-1);
					break;
				}
				if(key_2 == gap) {//큰 제곱수와 gap이 같을 때
					printf("%lld\n", 2*i+1);
					break;
				}
				if(key_2 > gap && gap >= key_3) //절반으로 나눈 뒤 큰 제곱수와 더 가까이 있을 때
				{
					printf("%lld\n", 2*i+1);
					break;
				}
				if(key_1 < gap && gap < key_3) //절반으로 나눈 뒤 작은 제곱수와 더 가까이 있을 때
				{
					printf("%lld\n", 2*i);
					break;
				}
			}
			else if(key_1 > gap) i--; //만약 지나쳤다면, 1씩 줄이면서 두 제곱수 들 사이에 gap이 있을 곳을 찾는다.
			else i = i*10; //i을 1씩 늘리면 너무 느리므로 10씩 곱해준다!
		}
		t--;
	}
	
	return 0;
}

 

 

• 풀이

두 곳의 거리에 대한 공간 이동 장치 작동 횟수의 최소 값

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번]

 

1, 4, 9, 16은 각각 1*1, 2*2, 3*3, 4*4인 제곱수이다.

또한 제곱수 들은 공간 이동 장치 작동 횟수의 최솟값이 2n-1임을 알 수 있다.

 

그리고 두 제곱수 들의 사이에 있는 수의 공간 이동 장치 작동 횟수의 최솟값은 중간을 기준으로 더 큰 제곱수에 가까운 쪽은 더 큰 제곱수의 최솟값과 같으며, 반대는 작은 제곱수의 최솟값에 +1을 한 것과 같다.

 

위의 원리를 이용하여, 반복문을 통해서, 공간 이동 장치 작동 횟수의 최솟값들을 구했다.

 

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

1011번: Fly me to the Alpha Centauri