[백준] 알고리즘 수업 - 점근적 표기 1

알고리즘 수업 - 점근적 표기 1

이 문제는 실버V 수준의 어렵지 않은 문제입니다. 그런데 제출된 풀이가 계속 맞지 않아 결국 시간 절약을 위하여 풀이를 참조하였습니다. 그런데 도저히 다른 사람의 풀이가 명확히 이해가 가지 않았습니다. 답만을 맞추는 것을 실력향상에 도움이 되지 않기 때문에 결국 수학적으로 혼자 다시 풀었습니다. 이 문제의 다른 분들의 풀이에 의문을 가지실 저와 같은 사람이 있을거 같아 풀이를 적기로 하였습니다. 이 문제 풀어보지 않은 분들은 위 링크를 따라 먼저 혼자 풀어볼 것을 권장합니다.

우선 이 문제는 아래와 같은 표기 법을 검증하는 문제입니다.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

문제에서 아래와 같은 수식을 뽑아낼 수 있습니다.
f(n) = a1 * n + a0
g(n) = n
g(n)에 대한 것은 "O(n) 정의를 만족하는지" 이 문구에서 n = g(n)라는 사실을 알게 되는 것입니다.

다시 혼자 이 문제를 풀 때 기본적으로 한 생각은 실제 수식을 성립시키는 n을 구하여 주어진 n0과 비교하자는 것이었습니다. 그렇게 수학적으로 문제의 개념을 바꾸면 실제로 계산하여야 할 것은 중학교 수준의 부등방정식을 푸는 것입니다.

f(n) ≤ c × g(n)
a1 * n + a0 <= c * n  <<-- 위에서 정의한 수식을 적용
a0 <= (c - a1) * n

즉 위의 수식은 a0 <= (c-a1) * n 이 수식에 대해서 만족시키는 n을 찾거나 만족시키지 않는다는 것을 확인해야 합니다.
이 간단한 부등식이 성립하기 위하여 (c - a1)에 대하여 아래와 같은 3가지 조건을 살펴볼 수 있습니다.

1. (c - a1) == 0
위와 같은 경우 c-a1가 0이 되는 경우 a0 <= 0인 경우 n에 관계 없이 식이 성립합니다.

2. 0 < (c - a1)
위와 같은 경우 수식을 아래와 같이 바꿀 수 있습니다.
a0 / (c - a1) <= n
이 때는 a0 / (c-a1)를 계산하면 성립을 위한 최소 n을 구할 수 있으며 문제와 같은 경우 주어진 n0이 최소 n보다 크면 식이 성립합니다.

3. (c - a1) < 0
위와 같은 경우 수식을 아래와 같이 바꿀 수 있습니다.
a0 / (c - a1) => n
잠시 부등방정식에 대한 기억이 가물한 분들을 위하여 설명하자면 부등방정식은 양변에 -을 곱하거나 나눌때 부등호가 바뀝니다. 이럴 경우는 최대 n까지 식이 성립합니다.
그런데 이 경우 수식의 정의인 "모든 n ≥ n0"을 만족해야 한다는 조건에 의하여 모든 경우에 수식이 만족되지 않습니다.

이와 같은 내용을 바탕으로 코드를 작성하면 아래 같은 코드가 나옵니다.

#include <iostream>

using namespace std;


int main(int argc, char* argv[])
{
	int a1, a0, c, n0;
	cin >> a1 >> a0 >> c >> n0;

	if (c-a1 == 0)	
	{
		cout << (a0 <= 0);
	}
	else if (0 < c-a1)
	{
		int minN = a0 / (c-a1);
		minN += (double(a0) / double(c-a1) - double(minN) > (double)0.0 ? 1 : 0);
		cout << (minN <= n0);
	}
	else // c-a1 < 0
	{
		int maxN = a0 / (c-a1);
		cout << 0;
	}
	
	return 0;
}

위의 코드에서 minN을 구할 때 doube 연산을 이용하여 1이나 0을 더하는 부분은 예를 들어 설명하자면 1.2와 같은 최소 값은 2가 되지만 1.0와 같은 경우는 1이 되기 때문입니다.