백준 24313번 [알고리즘 수업 - 점근적 표기 1](C++)-yes6686- 티스토리

백준 문제 풀이: 24313 [알고리즘 수업 - 점근적 표기 1]

---

문제 링크: https://www.acmicpc.net/problem/24313

문제 설명:

주어진 함수 f(n) = a1 ⋅ n + a0와 상수 c, 그리고 특정 자연수 n0가 주어질 때, 다음 조건을 만족하는지 확인하는 문제입니다:

f(n) ≤ c ⋅ g(n) ∀ n ≥ n0

여기서 g(n) = n입니다. 위 조건을 점근적 표기로 나타내면 f(n) ∈ O(g(n))가 성립하는지 확인해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int a1, a0; // f(n) = a1 * n + a0의 계수
    cin >> a1 >> a0;

    int c; // 상수 c
    cin >> c;

    int n0; // 자연수 n0
    cin >> n0;

    // 조건 확인
    if (a1 > c) {
        // f(n) ≤ c * g(n)을 만족할 수 없음
        cout << 0 << '\n';
    } else {
        // f(n) ≤ c * g(n) 검증
        if (a1 * n0 + a0 <= c * n0) {
            cout << 1 << '\n'; // 조건 성립
        } else {
            cout << 0 << '\n'; // 조건 불성립
        }
    }

    return 0;
}

예제 입력:

1 1
2
1

예제 출력:

1

---

코드 설명

• 핵심 알고리즘: 함수 f(n)가 상수 c와 함수 g(n)를 사용한 조건을 만족하는지 확인합니다.
• 구현 세부사항:
  • 먼저, a1 > c라면 조건을 만족할 수 없으므로 0을 출력합니다.
  • 그 외의 경우, f(n0) = a1 ⋅ n0 + a0가 c ⋅ n0 이하인지 검증합니다.
• 시간 복잡도: 모든 연산은 상수 시간에 수행되므로 O(1)입니다.

---

결과

입력된 f(n), c, n0에 대해 점근적 표기 조건이 성립하는지 확인하고, 조건 성립 여부를 1 또는 0으로 출력합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!