문제 URL:
1011번: Fly me to the Alpha Centauri
우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행
www.acmicpc.net
다음 문제는 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";
}
}