[BOJ] 백준 24313 알고리즘 수업 - 점근적 표기 1 (Swift)

문제

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

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

풀이

조건을 잘 확인해보고, 예제 입력을 보면 $O(n)$을 만족시키는 조건을 찾을 수 있습니다.
첫 번재 줄에서, $a_1 * n + a_0$ 가 $f(n)$ 입니다.
두 번째 줄에서, $c$ 세 번째 줄에서 $n_0$를 입력 받고, $c * n$ 이 $g(n)$ 입니다.

그렇다면, $a_1 * n + a_0 \le c * n$에서 $n_0$를 대입해서 확인해보면 되겠죠?

하지만, 한가지 조건이 더 있습니다.
바로, $a_0$가 음수인 경우입니다.

예를들어, $5n - 2 \le 3n$ 이고, $n_0 = 1$ 이라면?
1일 때, 만족합니다. $(3 \le 3)$

하지만, 2일 때는 만족하지 않습니다. $(8 \le 6)$

따라서 $a_1 \le c1$ 이여야 합니다.

두가지 조건을 만족하면 1, 아니라면 0을 출력해주면 됩니다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a1 = input[0], a0 = input[1]
	let c = Int(readLine()!)!
	let n = Int(readLine()!)!
	a1 * n + a0 <= c * n && c >= a1 ? print(1) : print(0)

view raw 알고리즘 수업 - 점근적 표기 1.swift hosted with ❤ by GitHub

후기

$a_1 \le c1$ 조건을 빼먹기가 쉬운 문제인 것 같습니다.
저도 맨 처음에는 빼먹고 작성하였고, 조건을 잘 살펴본 후, 모든 $n \ge n_0$에 만족해야 한다는 것에 힌트를 얻어 음수를 떠올릴 수 있었습니다.