[알고리즘] 백준 11561번: 징검다리 (C++), 등차수열의 합, 이젠 수학까지 해야 하니

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

11561번: 징검다리

이번 문제는 수학 카테고리에 넣고 싶었으나 그래도 문제의 베이스는 이분 탐색이라서 이 카테고리에 넣어둔다.

점프를 최대로 하려면 1칸 점프를 한 뒤, +1 점프, +1 점프로 목적지에 도달해야 최댓값이 도출될 수 있다.

 

하지만, 100칸이 있을 때는 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14까지 더하면 100이 넘는다.

그래서 이럴 경우에는 13번째 점프를 할 때, 100을 채우게끔 22칸을 뛰어주면 된다.

즉, 코드로 구현을 할 때는 value가 입력 값으로 들어오면 저 값이 넘지 않는 최댓값을 구해주면 된다.

---

솔루션

value로 들어올 수 있는 값의 범위가 엄청 크기 때문에 이때 이분 탐색을 사용해야 한다.

하지만, 시간 초과가 났었다 이유는 합을 구하는 과정에서 더하기 연산이 무수히 많이 일어나기 때문이다.

 

그래서 이번 문제의 키워드는 그 합을 어떻게 시간을 줄여서 구할 것인지가 중요하다.

>> 등차수열의 합 사용

이번 문제의 핵심 키워드는 2개였다.

1) 최댓값은 1부터 시작하는 차수가 1인 등차수열을 구해야 한다는 점

2) 등차수열의 합을 시간적인 측면에서 공식을 사용하여 빠르게 구한다는 점

#include <iostream>
#include <algorithm>
using namespace std;
#define ll unsigned long long

int T;
// n이 주어졌을 때, n부터 1까지 더한 값이 value를 넘으면 X
// value보다 작거나 같으면 O

bool sol(ll mid, ll value) {
	// 등차수열의 합
    // 소수점이 사라질까 걱정 안 해도 되는 이유는
    // +1을 해버리면 둘 중에 무조건 하나는 짝수이기 때문이다.
	ll sum = mid * (mid + 1) / 2;
	return sum > value;
}
int main() {
	cin >> T;
	ll value;
	for (int i = 0; i < T; i++) {
		cin >> value;

		ll low = 1;
		ll high = value;
		ll answer = 0;
		while (low <= high) {
			ll mid = (low + high) / 2;

			if (sol(mid, value)) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
				answer = mid;
			}
		}
		cout << answer << '\n';
	}
	return 0;
}