백준 1011_Fly me to the Alpha Centauri.cpp

<소스코드>

#include <iostream>
using namespace std;
int main(){
    int NumTestCases;
    cin >> NumTestCases;
    for(int i = 0; i < NumTestCases; i++){
        long long x, y;
        cin >> x >> y;
        long long cnt = 0;
        long long k = 1; // 속도
        long long position = x; //현재위치

        while(position != y){
            position += k;
            cnt++; 
            //cout << position << " ";
            if(y-position >= (k+2)*(k+1)/2){
                k = k+1;
            }else if(y-position >= (k+1)*(k)/2){
                k = k;
            }else{
                k = k-1;
            }
        }
        cout << cnt << '\n';
    }
}

1. 변수
   long long x, y : 입력받는 시작점과 끝점
   long long cnt : 이동한 횟수
   long long position : 현재위치
   long long k : 속도

2. 알고리즘
   1) 시작은 무조건 1로 출발하기 때문에 k와 position의 값을 1, x로 초기화 해둔다.
   2) 어차피 도착할 때 속도는 1이어야 하기 때문에 만약 현재 속도가 3이라면 3->2->1 이런식으로 줄어들면서 와야 된다.
   즉 남은 거리(y=position)과 현 속도부터 도착 속도까지의 총 합의 관계에 따라서 속도를 정할 수 있다. 예시를 들어보겠다.
   x : 1 y : 15
   y-position | k | 다음 k값
   15-2 >= 3(2,1) 이런식으로 속도를 하나 올렸을때의 총합보다 남은 거리가 크다면 k+1로 변경
   15-4 >= 6(3,2,1) ==> k+1
   15-7 < 10(4,3,2,1) 이런식으로 총합이 더 클 경우 k값 그대로 유지한다
   15-7 >= 6(3,2,1) ==> k
   만약 현재값보다 더 작아지면 그땐 k-1
   여기서 총합은 자연수의 합 공식인 : (k)*(k+1)/2를 활용하고
   k값이 변할때마다 cnt++;

3. 배운점
   
   이런식으로 규칙을 찾아서 푸는 방법도 있는데 대단한거 같다 확실히 나보다 계산량이 줄어드니까 훨씬 더 좋은 방법인 거 같다

4. 아쉬운점&느낀점
   처음에 정말 여러가지 방법으로 고민을 해봤다. 엄청나게 나열만 하기도 했고 그러다보니 규칙을 찾을 수 있었다. 확실히 기본수학 알고리즘을 공부하면서 수학적인 머리가 다시 살아나는 느낌이 좀 있는거 같긴하고, 정말로 뿌듯했다. 그렇지만 범위는 늘 조심하지. 진짜 범위가 좀 크다 싶으면 무조건 long long 쓰자 제발..!!