[백준] 1011번 - Fly me to the Alpha Centauri (골드 5)

1. 문제 

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

1011번: Fly me to the Alpha Centauri

---

2. 코드

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ll;

int main() {
    int int_case;
	ll x, y, res,distance, level;
    
	cin >> int_case;

	for (int i = 0; i < int_case; i++) {
		cin >> x >> y;
		distance = y - x;

		if (distance > 0 && distance <= 3) {
			res = distance;
		}
		else {
			level = (int)sqrt(distance);

			if (((level + 1) * (level + 1)) - (level+1) < distance && distance < ((level + 1) * (level + 1))) {
				res = 2 * level+1;
			}
			else if (distance == level * level ) {
				res = 2 * level -1;
			}
			else {
				res = 2 * level;
			}
		}

		cout << res << "\n";
	}
    return 0;
}

---

3. 결과

백준 입출력

 

---

 

4. 문제 풀이 방식

•  가능한 경우의 수를 모두 계산하여 최소의 개수를 찾는 방법 -> 시간 부족으로 인한 실패
•  재귀함수를 작성하여 위와 같은 방식을 구현 -> 구현 실패
•  각 거리 별 결과를 직접 작성하여 패턴을 분석 -> 특정 경우에서 자리수가 증가하는 모습이 보여짐
•  해당 패턴을 기반으로 코드를 작성하여 제출 -> 50%에서 틀림
•  반례를 확인 -> 작성한 코드에선 문제에서 주어진 가장 큰 수 (2147483647)의 처리가 불가
•  자료형을 int -> unsigned long long으로 변경
•  거리가 제곱근의 제곱과 같은 경우 결과에 -1을 해주어야 함
  ex) 거리가 9인경우 제곱근은 3이고, 자리수도 3 (2 * 2 - 1 = 3)
•  아래는 분석한 자료임

패턴 찾기