백준 1011번 C언어

규칙을 찾거나 움직인 방식을 보는 문제.
규칙을 찾는게 이해가 쉬워서 표를 그려서 확인해본다.

1. 움직일 거리에따라 이동 방식이 동일함.
2. 이동방식을 보면 패턴이 1 + 2 + .. + n + (n - 1) + .. + 1 인데, 이것은 n 제곱이다. (1+2+..+n이 n*n-1/2니까.)
3. 이동방식에서 최댓값의 제곱근과, 총 움직인 횟수 차이점을 보면 패턴이 보임
4. 수식을 만들어 풀면 됨

// distance : y - x
// sqrt_ : 루트 (y - x)

#include <stdio.h>
#include <math.h>

int main(void){
    int n;
    long long sqrt_, distance;
    long long x, y;
    
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++){
        scanf("%lld %lld", &x, &y);
        distance = y-x;
        sqrt_ = sqrt(y-x);
        
        if(distance == sqrt_*sqrt_){    
        // 제곱이랑 같으면,
            printf("%lld\n", 2 * sqrt_ -1); // 움직인 횟수
        }
        else if(sqrt_*sqrt_ < distance && distance <= sqrt_*sqrt_ + sqrt_){
        // 제곱보다 크거나 제곱에서 제곱근 하나 더한거 사이면,
            printf("%lld\n", 2 * sqrt_);  // 움직인 횟수
        }
        else { 
        // distance < sqrt_*sqrt_ + sqrt_ && distance < (sqrt_+1)*(sqrt_+1)
        // 그 사이가 아니면, 
            printf("%lld\n", 2 * sqrt_ + 1); // 움직인 횟수
        }
    }
    return 0;
}

참고
링크텍스트
링크텍스트