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

문제 설명

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

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

 

접근 방법 - 함수에 대한 수학적 이해 문제

백준의 24313번 문제는 함수에 대하여 수학적인 이해를 요구하고 있는 문제이다.

해당 문제는, 문제에 있는 빅오표기법에 있어 주어진 입력값에 대하여 식이 성립되는지를 정답으로 출력해야 하는 문제이다.

복잡하게 설명되어 있지만, 각 예제 입출력에 있는 힌트들만 유심히 보면 쉽게 해결할 수 있는 문제이다.

아래와 같이 식을 구성하고 각 입력값을 적용하면 어렵지 않게 해결할 수 있을 것이다.

1. f(n) <= c * g(n)에 대해, 식이 성립되는지를 확인해야 한다.
2. 이때 문제에서 O(g(n))을 O(n)로 축약하였기 때문에, g(n) = n으로 적용하면 된다.
3. 그리고 문제에 있는 대로, f(n) = a1 * n + a0임도 알 수 있다.
=> 각각 대입하면, a1 * n + a0 <= c * n으로 식이 완성된다.

위처럼 식 유도를 하였다면, 이 이후로 a1, a0, c, n은 입력으로 주어지기 때문에 각각 대입하여 식이 성립되는지만 확인하면 된다. 

(이때 n>=n0로 인해 n값을 하나로 특정 지을 수 없는 것은 사실이다. 다만 a1과 c가 양수라는 점을 통하여, n0인 경우만 성립된다면 이 외의 경우 또한 모두 동일하게 성립된다는 점을 알 수 있다.)

위 원리를 통하여 아래의 코드를 작성하였으므로, 위 설명과 아래의 코드를 함께 참고하면 좋을 것이다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) a1, a0, c, n0의 값을 순차적으로 입력받는다.

(필자의 코드에선 각각 n1, n2, c, g 변수로 입력받고 있다.)

 

2) 참/거짓 여부를 저장할 변수 tmp를 선언하고, 위 설명에 있는 식에 입력값을 대입한 조건식의 결괏값으로 변수를 초기화한다.

(이때, 변수 tmp는 boolean이어도 int여도 크게 상관없다. 식의 참/거짓 여부는 0과 1로도 반환이 가능하다.)

 

3) 현재 저장된 tmp의 값을 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 24313번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);   cout.tie(NULL);

	int n1, n2;
	cin >> n1 >> n2;

	int c, g;
	cin >> c >> g;

	int tmp = n1 * g + n2 <= c * g && n1 <= c ? 1 : 0;
	cout << tmp << endl;
}

 

제출 결과

(2023.07.04 백준 24313번 문제 제출 결과)