알고리즘 문제

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

feelcoding 2020. 3. 1. 23:35
728x90

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

 

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을

www.acmicpc.net

출발지 x와 도착지 y 사이의 거리를 구하고 그 차이가

거리   이동횟수  
1 1의 제곱 1 (= 1 * 2 - 1) 1개 연속 1
2   2 1개 연속 2
3   3 2개 연속 3
4 2의 제곱 3 (= 2 * 2 - 1)
5   4 2개 연속 4
6   4
7   5 3개 연속 5
8   5
9 3의 제곱 5 (= 3 * 2 - 1)
10   6 3개 연속 6
11   6
12   6
13   7 4개 연속 7
14   7
15   7
16 4의 제곱 7 (= 4 * 2 - 1)
17   8 4개 연속 8
18   8
19   8
20   8
21   9 5개 연속 9
22   9
23   9
24   9
25 5의 제곱 9 (= 5 * 2 - 1)
26   10 5개 연속 10
27   10
28   10
29   10
30   10

이 규칙만 이용하면 된다

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


int main() {
	long long testCase;
	cin >> testCase;
	for (long long t = 0; t < testCase; t++) {
		long long x, y;
		cin >> x >> y;
		long long distance = y - x;
		if (sqrt(distance) == ceil(sqrt(distance))) cout << sqrt(distance) * 2 - 1 << '\n';
		else if (pow(floor(sqrt(distance)), 2) + floor(sqrt(distance)) >= distance) {
			cout << floor(sqrt(distance)) * 2 << '\n';
		}
		else cout << floor(sqrt(distance)) * 2 + 1 << '\n';
	}
	return 0;
}
728x90