BOJ - 1011. Fly me to the Alpha Centauri

 

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

1. 시작점과 끝점은 중요하지 않고, 그 사이의 거리가 중요합니다.

2. 처음 시작은 1 마지막 시작은 1로 끝나야 합니다.

3. 아이디어가 딱히 떠오르지않아서 막무가내로 다 그려보고 적어보니깐 규칙이 발견되었습니다.

거리	작동횟수
1	1
2	2
3	3
4	3
5	4
6	4
7	5
8	5
9	5
10	6
11	6
12	6
13	7
14	7
15	7

이 규칙에 맞게 코드를 작성해주니 몇줄안되는 간략한 코드가 나왔습니다.

 

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int a,b;
        cin>>a>>b;
        int dist = b-a;
        int x = sqrt(dist);
        if(dist == x*x){ 
            cout<<2*x - 1<<'\n';
        }else if(x*x+x<dist){ 
            cout<<2*x + 1<<'\n';
        }else{
            cout<<2*x<<'\n';
        }
    }
    
    return 0;
    }