백준문제풀이 11단계 시간 복잡도(7) 24313번 알고리즘 수업 - 점근적 표기 1 (C#)

 

간단하게 말해서

n ≥ n0인 모든 n에 대해 f(n) ≤ c * g(n)이 성립하는지 출력해주는 문제이다.

성립이 안된다면 0을 성립된다면 1을 출력해주면 된다.

 

입력으로는 첫줄에 함수를 나타내는 a1 a0가, 그대음으로 c와 n0가 입력된다.

 

복잡해 보이지만

식으로 풀어보자면 n0 <= n <= 100인 모든 n중에서 a1 * n + a2 ≤  c * n이 성립 하는가?를 보면 된다.

먼저 그대로 이렇게 식으로 써서 보면

 

using System;
class BackJoon
{
    static void Main(string[] args)
    {
    	string[] input = Console.ReadLine().Split();
        int a1 = int.Parse(input[0]);
        int a0 = int.Parse(input[1]);
        int c = int.Parse(Console.ReadLine());
        int n0 = int.Parse(Console.ReadLine());
        for (int i = n0; i <= 100; i++)
        {
            if (a1 * i + a0 > c * i)
            {
                Console.WriteLine(0);
                return;
            }
        }
        Console.WriteLine(1);
    }
}

 

이렇게 풀수있는데 i는 n부터 100까지 돌면서 식을 하나씩 확인한다.

모든 n에 이 식이 만족하면 1을 출력하게 된다.

 

하지만 for문을 안쓰고도 풀수있는데

a1 <= c && a1 * n0 + a0 <= c * n0

a1이 c보다 작거나 같은지를 보는 것이다.

 

이는 증가량을 보는것인데 n0에 곱해지는 a1과 c를 비교해서 a1이 c보다 같거나 작고

n0에 대해서 a1 * n0 + a0 <= c * n0 식을 만족한다면 모든 n에 대해서 만족하는것이다.

 

코드로 보면

using System;
class BackJoon
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int a1 = int.Parse(input[0]);
        int a0 = int.Parse(input[1]);
        int c = int.Parse(Console.ReadLine());
        int n0 = int.Parse(Console.ReadLine());

        if (a1 <= c && a1 * n0 + a0 <= c * n0)
            Console.WriteLine(1);
        else
            Console.WriteLine(0);
    }
}

 

이렇게 for문을 쓰지 않고도 풀 수가 있다.

 

이것으로 11단계 시간 복잡도가 모두 끝났다.

내일부터는 12단계 브루트 포스단계를 풀어보자.