[백준] Fly me to the Alpha Centauri (C++)

 

문제 URL:

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

 

다음 문제는 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램으로

공간이동 장치는 이전 작동 시기에 k광년을 이동하였을 때 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다.

 

문제 풀이는 다음과 같다.

 

• 처음과 끝이 반드시 1광년 이어야 하므로 이동 횟수의 최솟값을 구하려면
  처음과 끝이 대칭 형태로 진행한다고 생각.
  ex) 1광년-2광년-3광년-...-3광년-2광년-1광년
  
  
• 완전한 대칭 형태가 아니라면 최대한으로 대칭 형태를 만들어준 뒤 가운데 남는 공간을 생각해줌.
  여기서 남은 공간이 만약 (대칭 형태에 쓰인 광년 중 가장 큰 값)+1보다 작거나 같으면
  최소 이동 횟수는 (대칭 형태에 쓰인 광년 중 가장 큰 값)*2+1이고,
  크다면 (대칭 형태에 쓰인 광년 중 가장 큰 값)*2+2이다.→ 가운데 공간은 항상 2개의 광년으로 나뉠 수 있음.
  ex) 1-2-...-7-5-7-...-2-1         => 최솟값: 7*2+1=15 (5를 앞서 나온 5광년 옆으로 옮겨줌)
       1-2-...-7-9(1-8)-7-...-2-1 => 최솟값: 7*2+2=16 (9에서 나누어진 1을 1광년 옆으로 옮겨줌)
  
  
• 위 내용을 다음과 같이 구현했는데, 
  먼저 주어진 거리를 대칭 형태라고 생각하고 거리(y-x)에서 1광년부터 거리가 0이거나 음수가 될 때까지
  1광년씩 늘려가며 (광년)*2한 수만큼 반복해서 빼준다.
  
  이때, 거리가 음수가 된다면 거리는
  ((마지막으로 빼준 광년)*2+(마지막으로 빼준 광년-1)*2)/2한 값
  =가운데 남는 공간이 (대칭 형태에 쓰인 광년 중 가장 큰 값)+1인 상태
  을 기준으로 개수가 달라지기 때문에 이를 기준으로 이동 횟수의 최솟값을 다르게 설정한다.
  
  
• 주의할 점! 문제 속 x와 y의 범위는 int형의 범위인 -2,147,483,648 ~ 2,147,438,647를 벗어나게 되므로
  int형보다 범위가 더 큰 데이터 타입으로 x와 y를 선언해주어야한다.

---

#include<iostream>
using namespace std;

int main()
{
    int t; 
    double x, y;
    cin >> t;
    
    for(int i=0; i<t; i++)
    {
        cin >> x >> y;
        
        double n = y-x;
        double num = n;
        int a=1, count=0;
        double sum=0, result=0;
        
        while(num>0)
        {
            sum += a;
            num = num - a*2;
            count++;
            a++;
        }
        
        if(n > 2*(sum+(sum-count))/2)
            result = count*2;
        else
            result = count*2-1;
        
        cout << result << "\n";
    }
}