백준 - Fly me to the Alpha Centauri) 복습을 위해 작성하는 글 2023-12-27

📘 백준 - Fly me to the Alpha Centauri

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

📝 구현

// C++
//#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
    
	int t;
	cin >> t;
    
	for (int i = 0; i < t; ++i) {
		int x, y, count;
		cin >> x >> y;
        
		int distance = y - x; // 거리
		int close = floor(sqrt(distance)); // 루트 distance의 근사값(소수 자리 절삭)
		int count = close * 2 - 1; // 이동 횟수
		int remain = distance - close * close; // distance와 close^2의 차이
        
        // remain을 이용하여 예외 처리
		if (remain == 0)
			cout << count << '\n';
		else if (remain <= close)
			cout << count + 1 << '\n';
		else
			cout << count + 2 << '\n';
	}
    
	return 0;
}

👨‍💻 구현 설명

• 문제에는 수학 문제답게 규칙이 존재하는데 그 규칙은 아래와 같다.
• 규칙
  일단 최소 횟수를 구하는 것이기 때문에 숫자가 커져야 하는데, 아래와 같은 규칙이 생긴다.
  예) distance : 25인 경우
  1 2 3 4 5 4 3 2 1의 규칙이 발생 : 1부터 distance의 제곱근(소수 자리 절삭)까지 증가했다가, 다시 1까지 감소하는 규칙을 보인다.
  여기서 count는 close(distance의 제곱근) * 2 - 1의 규칙이 발생한다.
  단 예외가 존재하는데, 만약 예가 distance : 35인 경우라면
  1 2 3 4 5 5 5 4 3 2 1이 된다.
  때문에 distance - close * close를 해주어야 하고, 이 식의 해(remain)가 0과 같으면 count는 위 규칙에 따라 그냥 출력하면 될 것이고, remain <= close 라면 count + 1, remain이 close보다 크다면 count + 2라는 식을 적용하면 원하는 답을 구할 수 있다.
  
  

🙄 Thinking...

• 처음엔 문제를 잘못 이해하여 '도착 바로 직전의 이동 거리는 반드시 1광년'이 부분을 '뒤 숫자가 얼마나 크든 간에 마지막은 무조건 1거리로 한다.'로 착각하였다. (원래는 '마지막은 1광년이 와야 하니까 점차 줄어들면서 와야 한다.'라는 뜻인 것 같다.)그래서 처음에 좀 헤매기도 하였지만 위 조건으로 하면 문제가 쉽게 풀려야 할 것 같다는 생각과 무엇인가 놓친 것 같은 찜찜한 기분이 들어 문제를 처음부터 다시 이해해 보려고 노력했다.
• 문제를 이해하고 난 후 문제의 수학 문제답게 반드시 규칙이 존재할 수밖에 없다고 생각하였고 규칙을 찾고 난 후에는 수월하게 문제를 해결할 수 있었다.