[C++]백준 알고리즘 1011번

풀이는 아래와 같다.

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    int T;
    cin >> T;
    for(int testcase=0; testcase<T; testcase++){
        int x,y;
        cin >> x >> y;
        int d = y-x;
        
        int max = floor(sqrt(d));
        int ans = 0;
        
        ans += 2*max - 1;
        d -= max * max;
        
        for(int i=max; i>0; i--){
            while(d >= i){
                d -= i;
                ans++;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}
 

알고리즘 자체는 한번 잘 생각해보면 잘 해결할 수 있다.

우주선의 속도가 1,0,-1씩 변해야 한다는 점을 이용하였는데, 위의 코드에서 max란

해당 거리 d를 여행할 때 낼 수 있는 최대의 속도이다. 1부터 max까지, 그리고 max-1부터 1까지는

무조건 한번씩 들어가게 되고, 그 합은 max의 제곱이다. d- max*max인 나머지 거리는 max부터 1까지 내려가면서 최대한 끼워넣으면 된다. 이때 ans를 1씩 증가시키면 된다.

 

말이 쫌 내가 봐도 이상하니깐 알고리즘은 알아서 잘 생각해보길 바란다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ