백준 #1011 Fly me to the Alpha Centauri

이번 문제는 알파 센타우리까지 우주선을 타고 갈 때, 워프기계는 최소 몇번 작동으로 갈 수 있는지 구하는 문제입니다.

우주적인 문제이지만, 사실상 거리의 절반까지 가는데, 1+2+3+...+k 의 값이 거리의 절반보다 작으면서 가장 큰 수가 되는 것을 구하는 문제입니다.

 

알파 센타우리까지의 워프

 

알파 센타우리는 지구로부터 4.37 광년정도 떨어져 있습니다.  우주선이 빛의 속도로 가도 4.37년이 걸리는 곳입니다.

태양과는 주계열성으로는 가장 가까운 별이라서 지구에서 관측할 때 아주 밝게 빛나는 별입니다만, 아쉽게도 우리나라가 있는 위도상에서는 관측이 힘듭니다.

 

영화에서도 새로운 지구로 자주 쓰이는 별입니다.  영화 패신저스에서도 알파 센타우리가 쓰였죠.  가는데 백여년이 걸려서 사람을 동면시켜서 갑니다.  (사실상 그곳까지 가는 기술을 개발하는 것보다 사람을 동면시켜서 사람의 기능을 정지시키는 게 더 어려워 보입니다.)  그런데 현재 기술이면 실험적으로 20년정도 걸려서 무인우주선을 보낼 수 있다고 들었는데.  이온추진장치를 이용하면, 가능할 것이라고 생각합니다.

 

옆길로 샜는데요.  이 문제를 풀기 위해서는 1부터 n까지의 합이 주어진 거리 d보다 작으면서 가장 큰 값을 찾아야 합니다.

 

\[ 1 + 2 + 3 + ... + n = \sum_{k=1}^{n} k \le d \]

 

1 부터 n까지의 합 공식은 잘 알려진 것과 같습니다.  삼각수라고도 합니다.

 

\[ \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \]

 

우리는 이것을 이용해서 다음과 같은 2차 방정식을 풀면 됩니다.

 

\[ x^2 + x - 2d = 0 \]

 

이 중 양의 근은 일반적으로 실수가 나오겠죠.  이 근을 중심으로 단순증가이므로, 실수의 값 중 정수부만 취하면 우리가 원하는 답이 됩니다.

근의 공식을 이용했고, 실수의 라운드 오프 에러가 발생할 것을 방지하기 위해서 수치에 여분을 주었습니다.

 

아래는 제가 짠 소스입니다.  소스는 참고용으로만 봐주세요.

 

//----------------------------------------------------------------------------------------
//  baekjoon #1011 - Fly me to the Alpha Centauri
//    - by Aubrey Choi
//    - created at 2019-09-11
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>

int main()
{
  int t, x, y;
  scanf("%d", &t);
  while(t--)
  {
    scanf("%d%d",&x,&y); y-=x;
    if(y==1) { puts("1"); continue; }
    int r=(-0.9999+sqrt(1+4.0*y))/2.0;
    y-=r*(r+1);
    printf("%d\n", 2*r+(y+r)/(r+1));
  }
}