[백준/C++] 24313 알고리즘 수업 - 점근적 표기 1 (S4)

유형	난이도	완료일	링크	특이사항
시간복잡도	실버4	23/03/05	https://www.acmicpc.net/problem/24313

 

 

내 코드

#include <iostream>

using namespace std;

int main(void)
{
	
	int n;
	int a1, a2;
	int c;
	
	cin >> a1 >> a0 >> c >> n;
	
	int ans = 1;
	
	if(c-a1<0)
		cout <<0;
	
	else if(a0 <= (c-a1)*n)
		cout <<1;
	else
		cout <<0;

}

처음엔 문제가 선뜻 해석되지 않았다. 수식 표현에 익숙하지 않아서 그런 것 같다.

문제 조건 중 모든 n에 대해서 만족해야 한다는 내용이 있다. 이 때 n의 범위가 주어지지 않아 반복문으로 어떻게 확인해야 할지 막막했었는데, n0이 n 중 가장 작은 수 이므로,

a0 ≤ (c-a1) * n0 이 참이라면 n0보다 큰 나머지 모든 n에 대해서도 식이 참인 것을 알 수 있다.

그러나 c-a1이 0보다 작고 a0이 음수인 경우 오른쪽 식이 n의 증가에 따라 더 작아져서 나중엔 식이 거짓일 수 있다. 따라서 c-a1인 경우에도 0을 출력해야 한다.