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

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

이번 문제는 길어서 풀이만 쓰도록 할게요!

---

풀이

Algorithm

1. 먼저 어떻게 count를 해줄 지 생각을 해봅니다.
   • 우선 이 문제는 x, y가 어떤 수인지 보다 두 행성 사이의 거리(x-y)가 중요한 판단 지표라는 것을 알아야 합니다.
   • 그리고 x-y가 아주 큰 수라고 가정을 했을 때, k1, k2, k3,..., kn은 차례로 1, 2, 3, 4, ..., 4, 3, 2, 1이런 식의 순서로 나타나야만 하겠죠?
   • 그렇다면 양쪽에 모두 존재하는 수의 최댓값과, 중간에 있는 수가 count를 판별하는 중요한 지표가 됩니다
   • (양쪽에 모두 존재하는 수의 최댓값*2 + 중간에 있는 수의 개수)이 결국 count가 될것이에요
   • 예를 들어 설명하자면 거리가 16일 때, k는 차례로 1, 2, 3, 4, 3, 2, 1의 순서로 나타나겠죠? 그리고 이때 양쪽에 모두 존재하는 수의 최댓값은 3이고, 중간에 있는 수는 4로 1개라서 총 3*2 + 1 = 7회 작동되어야 해요
2. count 알아내기
   • 우선 양쪽에 모두 존재하는 수의 최댓값을 구하는 방법은 while문을 통해 x에 1부터 차례로 곱하기 2를 한 값을 순서대로 빼보는 거예요.
   • 루프를 돌 때마다 temp를 1씩 증가시키며 x-=temp; 해주다가, x가 temp*2보다 작거나 같아지는 순간 while문 루프를 빠져나와야겠죠?
   • 이 루프를 한번 돌 때 양쪽에 수가 두 개씩 있다는 의미이니까 count+=2;를 해주어야 해요.
   • 그리고 루프를 빠져나왔을 때의 temp와 x를 통해 중간에 있는 수의 개수를 판별할 수 있어요.
   • 만일 x(중간에 있는 수의 합)가 temp보다 큰 경우, x는 한 개의 수로 이루어진 것이 아니니, count+=2;를 해주어야 해요.
   • 그렇지 않다면 x는 한개의 수로 이루어져있을테니, count++;를 해줍니다. 
3. 예외 상황 따져보기
   • 여기에서 예외 상황은 아예 while문을 돌게 되지 않는 경우인데요, 이는 거리가 1 또는 2인 경우예요.
   • 거리가 1이면 횟수도 1이고, 거리가 2이면 횟수도 2이겠죠?(k1 = 1, k2 = 1)
4. 이를 코드로 표현해주고 count를 출력해줘요
5. 끝~!

 

code

#include <iostream>
using namespace std;

int main() {
	int T, x, y, temp, count; // temp는 숫자가 몇까지 올라갔는지 나타내는 변수, count는 횟수를 세는 변수입니다
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> x >> y;
		temp = 1;
		count = 0;
		x = y - x; // 두 수의 차이를 x에 저장
		if (x == 1 || x == 2) // 예외 상황
			count = x;
		else {
			while (x > temp * 2) {
				x -= temp * 2;
				temp++;
				count += 2;
			}
			if (temp < x) count += 2;
			else count++;
		}
		cout << count << '\n';
	}

	return 0;
}