[백준 1011] Fly me to the Alpha Centauri (C++)

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

1011번: Fly me to the Alpha Centauri

 

 

 

아이디어

마지막이 1로 끝나도록 일단 나열을 해봤는데 아래와 같았다.

숫자	식	횟수
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+2+1	7
14	1+2+3+3+2+2+1	7
15	1+2+3+3+3+2+2+1	8
16	1+2+3+4+3+2+1	8

제곱수마다 새로운 숫자가 나타나는 것을 볼 수 있다. (4의 경우 2 등장, 9의 경우 3등장) 그리고 제곱수의 경우 1+2+3+..n+n-1+n-2+...1 즉 횟수는 항상 수의 제곱근 +1이다. (4의 경우 루트4+1. 즉 3이다.)

그리고 5 6 7 8을 보면 56의경우 4번, 78의 5번인데 6은 2+4로 나타낼 수 있다는 사실에 주목하자.

비슷한 예시로 9와 16사이에서 횟수가 바뀌는 부분인 12역시 3+9이다. 코드로 나타내면 아래와 같다.

 

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	long long a, b;
	cin >> T;
	while (T != 0) {
		cin >> a >> b;
		int go =(int)sqrt(b - a);

		if (b - a < 4) {
			cout << b - a<<"\n";
		}
		else {
        //제곱수의 경우 ex)4
			if (b - a == go * go) {
				cout << 2 * go - 1 << "\n";
			}
            //거리+거리의 제곱근보다 클 경우 ex)7,8
			else if (go * go + go < b - a) {
				cout << go * 2 + 1 << "\n";
			}
            //거리+거리의 제곱근보다 작을 경우ex)5,6
			else {
				cout << go * 2 << "\n";
			}
		}

		T--;
	}
}