[C]백준 08.기본수학1: 1011

백준 1011

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int t;
	scanf("%d", &t);
	for (int m = 0; m < t; m++) {
		long long int distance;
		long long int x, y;
		scanf("%lld %lld", &x, &y);
		distance = y - x;
		long long int flag = 1;
		long long int sum = 0;
		long long int cnt = 0;
		long long int remain = 0;
		if (distance == 1) {
			printf("%d\n", 1);
		}
		else if (distance == 2) {
			printf("%d\n", 2);
		}
		else {
			while (distance >= (flag + 1) * (flag + 1)) {
				flag++;
			}
			sum = flag * flag;
			remain = distance - sum;
			if (flag > 1) {
				cnt = 2 * flag - 1;
				while (remain > 0) {
					if (flag > remain) {
						flag--;
					}
					else if (flag <= remain) {
						remain -= flag;
						cnt++;
					}
				}
			}
			else {
				cnt = 3;
			}
			printf("%lld\n", cnt);
		}
	}
	return 0;
}

 

		거리합	이동횟수	한번에 이동할 수 있는 최대 거리
1	1=	1	1	1
2	1+2+1=	4	3	2
3	1+2+3+2+1=	9	5	3
4	1+2+3+4+3+2+1=	16	7	4
5	1+2+3+4+5+4+3+2+1=	25	9	5
i		i^2	2*i-1	i

주어진 거리에 따라 한번 이동할 때 가는 최대거리가 정해져 있다. (예를 들어 거리가 6이라면 조건에 따라 절대 3만큼 이동이 불가능하고, 최대 2만큼밖에 이동하지 못한다. )

왜냐하면 n>3일때 n을 한번 이용해서 이동하려면 그 앞 뒤에 꼭 n-1이 있어야 마지막을 1로 마무리할 수 있기 때문이다. (예를 들어 4를 한번 이용하려면 4의 앞 뒤에 꼭 3이 존재해야하고, 또 그 3을 이용하려면 3의 앞 뒤에 꼭 2가 존재해야하기 때문이다.)

따라서 주어진 거리 distance가 i<=distance<(i+1)^2이라면 이때 한번에 이동할 수 있는 최대거리는 i이다. 그렇게 되면 distance의 구성은 1+2+3+...+i+...+3+2+1 이런 식에 남은거리를 i이하의 수로 끼워넣어줘야한다. 그리고 이때까지의 이동횟수는 2*i-1이다.

이동횟수를 최소로 하기 위해서는 남은 거리를 최대한 높은 수로 채워야 한다. 그런데 남은 거리는 i보다 클 수도, 작거나 같을 수도 있다. 만약 남은 거리가 i보다 클 경우 i를 1감소시키고, 남은 거리가 i보다 작거나 같으면 남은거리에 i를 빼고 이동횟수를 1증가시킨다. 이를 남은 거리가 0이하가 될때까지 반복시키면 주어진 거리에 따라 최소 이동횟수를 구할 수 있다. (나는 i를 flag 변수로, 남은거리를 remain 변수로, 이동횟수를 cnt 변수로 설정해서 코드를 짰다.)

이 문제를 풀 때 주의할 점은 거리가 1, 2일때를 고려해야 한다는 점이고, x,y가 2^31미만의 수이기에 int로는 처리할 수 없다는 점이다. 

https://www.acmicpc.net/board/view/26059 이 링크에 가면 코드가 맞았는지 확인할 수 있는 테스트케이스가 있다.