[BOJ/백준] 1011번 Fly me to the Alpha Centauri C++ 문제 풀이

단계별로 풀어보기 - 수학 1 단계 - [8단계] 1011번

문제

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

1011번: Fly me to the Alpha Centauri

입력 복사 : 

3 0 3 1 5 45 50

 

풀이

y - x	이동	작동횟수
1	1	1
2	11	2
3	111	3
4	121	3
5	1211	4
6	1221	4
7	12211	5
8	12221	5
9	12321	5
10	123211	6
11	123221	6
12	123321	6
13	1233211	7
14	1233221	7
15	1233321	7
16	1234321	7
17	12343211	8
18	12343221	8

 

위 표는 y-x에 따라 최소 작동횟수로 이동할 때, 이동변화와 작동횟수이다.

표시한 y-x는 i*i라고 표기할 수 있는 제곱수이다.

y-x가 제곱수일 때를 기준으로 다음 y-x에 작동횟수가 변하는 것을 볼 수 있다.

또한, 제곱수(i * i)와 그 전 제곱수((i-1) * (i-1))의 중간값에서 작동횟수가 증가한다.

 

※주의할 것※은 이번 문제에서 입력 값의 범위는  2^31까지라는 것이다.

우리가 주로 쓰는 int형의 범위인 -2,147,483,648 ~ 2,147,438,647를 벗어난다.

따라서 double형으로 변수를 선언하여 사용하였다.

 

CODE

#include <iostream>
using namespace std;

int main() {
	int T;
	cin >> T;
	for (int test_case = 0; test_case < T; test_case++) {
		double x, y, result;
		cin >> x >> y;

		double i = 1;
		for (;; i++) {
			if (y - x < i*i)
				break;
		}

		//거리가 i-1의 제곱수일때
		if (y - x == (i - 1)*(i - 1)) {
			result = 2 * (i - 1) - 1;
		}
		//거리가 i-1의 제곱수와 중간값 사이에 있을 때
		else if (y - x < ((i - 1)*(i - 1) + i * i) / 2) {
			result = 2 * (i - 1);
		}
		//거리가 중간값과 i의 제곱수 사이에 있을 때
		else {
			result = 2 * i - 1;
		}
		cout << result << '\n';
	}
}

 

결과