백준(1011번 Fly me to the Alpha Centauri)풀이 C++

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

1) 주석 없는 VERSION

#include <stdio.h>
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main() {
	int t;
	cin >> t;

	long long x, y;

	for (int i = 0;i < t;i++) {
		cin >> x >> y;
		double length = y - x;
		double a = sqrt(length);
		double b = round(sqrt(length));

		if (a <= b)cout << b * 2 - 1 << endl;
		else cout << b * 2 << endl;
	}

}

2) 주석 있는 VERSION

 

규칙을 찾아야하는 문제이다.

Length	이동	최소 이동 횟수	제곱근	제곱근 반올림	비교
1	1	1	1	1	=
2	11	2	1.414	1	>
3	111	3	1.732	2	<
4	121	3	2	2	=
5	1211	4	2.236	2	>
6	1221	4	2.449	2	>
7	12211	5	2.645	3	<
8	12221	5	2.828	3	<
9	12321	5	3	3	=

찾아낸 규칙은

제곱근(a), 제곱근 반올림(b) 를 비교 했을 때,

1) a<=b 일 때 최소 이동 횟수는 (2*b)-1

2) a>b 일 때 최소 이동 횟수는 2*b

 

그러므로 코드는 다음과 같이 짤 수 있다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <cmath> // sqrt와 round를 써주기 위해

using namespace std;

int main() {
	int t;
	cin >> t;

	long long x, y;

	for (int i = 0;i < t;i++) {
		cin >> x >> y;
		double length = y - x;
		double a = sqrt(length); // 제곱근
		double b = round(sqrt(length)); // 제곱근 반올림

		if (a <= b)cout << b * 2 - 1 << endl;
		else cout << b * 2 << endl;
	}

}

 

❌주의 사항❌

제곱근 찾을 때 : sqrt() 함수 사용

반올림 할 때 : round() 함수 사용