어떤 문제인가?

걍 수학문제다.

오잉?

이 문제에 총 3번 도전한 적이 있었다. 그 중 2번은 시도조차 못하고 나가떨어졌고, 결국 마지막에 성공했다.
무엇이 문제였을까?

문제에서 실마리를 찾다

첫 번째 시도에서는 피라미드 꼴, 그러니까 1,2,3,2,1 꼴을 만드는데 집착해 접근조차 할 수도 없었다.
두 번째 시도에서는 y-x와 작동 횟수 간 관계를 알아냈지만, 정수 차원에서 생각하면 될 것을 과도하게 실수 범위까지 해석해 문제에 맞는 모델을 찾을 수 없었다.

그래서 어떤 관계인지?

y-x가 제곱수 꼴일 때,작동 횟수의 최솟값은 2*\sqrt(y-x)-1 꼴로 결정된다.
어떠한 거리 D가 주어졌을 때, 최소한의 작동횟수 M(D)는,

• n = a^2 -> 2*-1
• a^2 < n <= a^2+a -> 2*a
• a^2+a < n <= (a+1)^2 -> 2*a+1
  꼴로 결정된다.

코드를 내놔라

내 코드다.

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

int main() {
    unsigned T,x,y,a,d,i=0;
    scanf("%u",&T);
    for(;i<T;i++) {
        scanf("%d%d",&x,&y);
        d=y-x;
        a=(unsigned)floor(sqrt((double)d));
        if(a*a==d) printf("%u\n",2*a-1);
        else if(a*a<d&&d<=a*a+a) printf("%u\n",2*a);
        else if(a*a+a<d<=(a+1)*(a+1)) printf("%u\n",2*a+1);
    }
}

남들은 어떻게 했나?

가장 인상적인 것으로, floor(sqrt(4*d+1))가 먹힌댄다. 어캐 구했대.

int main() {
	long long int a,b,c,d;
	scanf("%lld", &a);
	for (long long int i = 0; i < a; i++) {
		scanf("%lld %lld", &b, &c);
		d = c - b - 1;
		printf("%d\n", (int)sqrt(4 * d + 1));
	}
}

tapris님 풀이

• https://www.acmicpc.net/source/32175207