[BOJ 1011] Fly me to the Alpha Centauri

1) 문제 링크

https://www.acmicpc.net/problem/1011

2) 접근

짧지 않은 길이의 문제… 읽다가 한두 번 꼬이기도 했다. 어찌됐건 이해는 했는데, 당최 어떻게 접근해야 할지… 이럴 땐 늘 하던대로 특수한 case…를 먼저 접근하려 했지만 잘 안 보여서 걍 귀납적으로 시점과 종점의 거리를 1, 2, 3, 4… 로 설정하면서 때려박았다. 그러다 보니 답 사이의 규칙성이 보였고, 답이 바뀌는 경계가 되는 거리가 1X1, 1X2, 2X2, 2X3, 3X3, 3X4, … 식으로 올라가는 게 보였다. 이를 토대로 코드를 짜서 제출했고, 시간은 4ms가 떴다.

3) 풀이

#include <iostream>
#include <cmath>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    // cin.tie(NULL);

    int t, x, y;
    int root;
    cin >> t;

    for(int i=0; i<t; ++i){
        cin >> x >> y;
        root = int(sqrt(y-x));

        if(y-x == root*root) { cout << 2*root-1; }
        else if(y-x <= root*(root+1)) { cout << 2*root; }
        else { cout << 2*root+1; }
        cout << '\n';
    }
}

4) 피드백

풀면서도 굳이 if문 3개씩이나 써야할까 하는 생각이 들었다. 그래서 또 다시 최적해를 찾아보…려 했지만 내 코드랑 별반 다를 게 없었다. 걍 테스트를 위해 cin.tie를 주석 처리 한 거 때문에 4ms가 뜬 것. 주석 떼니까 0ms 떴다.