백준 1011번 문제(Fly me to the Alpha Centauri) C++로 풀기

1011번 Fly me to the Alpha Centauri 링크

---

문제 요약

어느 한 지점에서 다른 지점으로 이동하는데 최소로 필요한 이동횟수를 출력한다.

---

코드

#include <iostream>
#include <cmath>

using namespace std;

long solve(long a,long b)
{
  long dis=b-a; // 지점이 중요한 게 아니라 지점 간 거리만 있으면 됨
  long long j=1;
  while(j*j<=dis) // 제곱수
  {
    j++;
  }
  j--;
  long long rem=dis-j*j;  // 임시 변수
  rem=(long long)ceil((double)rem/(double)j);
  return 2*j-1+rem; // 최종 출력
}

int main()
{
  int t;
  scanf("%d",&t);
  for(int i=0;i<t;i++)
  {
    long x,y;
    scanf("%ld %ld",&x,&y);
    printf("%ld\n",solve(x,y));
  }
}

---

풀이

제곱수를 잘 이용해야 하는 문제이다.

---

주의점

입력값의 범위가 크기 때문에 int 형 말고 다른 자료형을 써야 안전하다.