백준 알고리즘 문제 풀이 c/c++ -1011-

https://www.acmicpc.net/problem/1011

• 각 횟수 별로 최대로 이동할 수 있는 거리를 각각 구한다
• 입력값들의 이동 거리를 구해서 위에서 구한 최대 거리들의 범위 중 속하는 부분을 찾는다
• 입력값 범위로 인해 long long int를 사용해야 하는 점 주의!

#include <stdio.h>
#include <algorithm>
#include <math.h> 
#include <string.h>
#include <vector>

using namespace std;


int main() {

	int T;
	scanf("%d", &T);

	for (int i = 0; i < T; i++) {

		vector <long long int> arr;

		arr.push_back(0);

		arr.push_back(1); // index 1 부터 계산하기 위함
		arr.push_back(2);

		long long int start, end;
		scanf("%lld %lld", &start, &end);

		long long int distance = end - start;

		if (distance == 1) {
			printf("1\n");
			
		}
		else if (distance == 2) {
			printf("2\n");
			
		}
		else {
			int cnt = 1;
			long long int add = 2;

			long long int result = 0;

			for (int j = 3; ; j++) {

				if (cnt <= 2) {
					long long int n = arr[j - 1] + add;
					arr.push_back(n);
					cnt++;
				}
				else {
					cnt = 2;
					add++;
					long long int n = arr[j - 1] + add;
					arr.push_back(n);
				}

				if (distance > arr[j - 1] && distance <= arr[j]) {
					result = j;
					break;
				}
			}

			printf("%lld\n", result);

			arr.clear();
			vector <long long int>().swap(arr);

		}


	}

	

	return 0;
}