[C++] 백준 1011 : Fly me to the Alpha Centauri

#include <iostream>
#include <cmath>

int T, x, y;
long long len;
int cnt, lenUp, lenDown;
int main(int argc, char **argv){
    scanf("%d", &T);
    for(int i = 0; i < T; i++){
        scanf("%d %d", &x, &y);
        len = y - x; // 거리
        
        lenUp = ceil(sqrt(len));
        lenDown = lenUp -1;
        
        if(len <= pow(lenDown, 2) + lenDown){
            cnt = lenDown * 2;
        } else {
            cnt = lenUp * 2 - 1;
        }
        printf("%d\n", cnt);
    }

    return 0;
}

감동의 첫 골드, 인터넷 코드를 하나도 참고하지 않았다!! 너무 뿌듯하다.

열심히 3시간정도 삽질한 과정

처음 작성한 코드

시간 초과가 떴다. 수학적으로 접근할 필요성이 있었다.

#include <iostream>

int T, x, y;
int cnt = 0, len = 0, sum = 0, idx = 1, db = 0;
int main(int argc, char **argv){
    scanf("%d", &T);
    for(int i = 0; i < T; i++){
        scanf("%d %d", &x, &y);
        len = y - x; // 거리
        
        while(sum < len){
            sum += idx;
            cnt++; db++;
            if(db == 2){
                idx++;
            }
        }
        printf("%d\n", cnt);
        cnt = 0; sum = 0; idx = 1; db = 0; 
    }

    return 0;
}