백준 24313 알고리즘 수업 - 점근적 표기

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

 

코드 참고

https://replit.com/@wny0320

wny0320 (박 상운)

 

---

24313

빅오 표기법을 이용해서 식을 계산하는 문제

using System;

namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            int[] aArray = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int a1 = aArray[0];
            int a0 = aArray[1];
            int c = int.Parse(Console.ReadLine());
            int n0 = int.Parse(Console.ReadLine());
            // 계산식 a1 * n + a0 <= c * n
            if (c < a1) // 이 경우 n0가 0일수 없으므로 a0가 0이더라도 (a1 - c) * n 이 양수로 성립이 불가능
            {
                //(a1-c) * n + a0 <= 0
                Console.WriteLine(0);
            }
            else if(c == a1) // 이 경우 a0 <= 0으로 a0가 0인 경우 항등식으로 성립
            {
                if (a0 <= 0)
                    Console.WriteLine(1);
                else
                    Console.WriteLine(0);
            }
            else
            {
                //c > a1인 경우, 식이 성립한다면 만족
                if (a0 <= c * n0 - a1 * n0)
                    Console.WriteLine(1);
                else
                    Console.WriteLine(0);
            }
        }
    }
}

식을 풀면서 주석으로 식에 대한 답들을 적었다.

 

1. c < a1인 경우 식이 성립할 수 없으며

 

2. c==a1인 경우 a0가 음수일때 성립가능

- 조건인 "절대값" a는 0이상 100이하, 즉 a값들은 음수값이 가능

- 초반에 절대값을 못보고 a0가 0일때 성립으로 해서 오류가 났었다.

 

3. c > a1인 경우 식을 만족한다면 성립

- 변형한 식 a0 / (c - a1)<= n, c > a1이기 때문에 양수이므로 부등호는 유지

- n >= n0이기 때문에 위의 식에서 a0 / (c - a1)<= n0 <= n인 것으로 생각할 수 있다.

- n의 최소값인 n0이 식을 만족하면 모든 n이 만족한다고 생각하면 된다.