글 작성자: 취업중인 피터팬
728x90

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

 

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

f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다.

www.acmicpc.net

 

문제 설명

 

시간복잡도의 탈을 쓴 수학 문제입니다. 

 

문제 풀이

 

이건 시간 복잡도에 대해 몰라도 됩니다.

오히려 함수 정의에 대한 이해가 필요한 문제입니다.

이것저것 기호가 많아서 어렵다고 느껴질 수 있는데 사실 별거 없으니 차근차근 한번 보겠습니다.

O(g(n)) = {f(n) | 모든 n>=n0에 대하여 f(n) <= c*g(n)인 양의 상수 c와 n0가 존재한다.} 

해당 문장을 분석하는 것이 제일 중요합니다.

 

O(g(n)) = f(n)입니다. 중괄호 안에 |앞은 "해당 함수는 | ~를 정의합니다."라는 뜻으로 O(g(n)) =  f(n)으로 가정하여도 됩니다. 그 말인 즉, g(n) = n이라는 말과 같습니다. 여기서 g(n) = n이라는 식을 구할 수 있습니다.

 

다음으로 넘어가겠습니다. "f(n) <= c*g(n)인 양의 상수 c와 n0가 존재한다".라는 뜻은 c와 n0가 양의 상수라면

f(n) <= c*g(n)를 만족해야 한다는 뜻입니다. 문제 밑에서 (1 <= c <= 100), (1 <= n0 <= 100)라는 조건이 있으므로 해당 식은 무조건 만족해야 O(n)이 만족할 수 있다는 것을 알 수 있습니다.

즉, f(n) <= c*n이라는 것입니다. 여기서 조금 더 나아가서 문제 밑에 f(n)에 대한 정의가 있습니다.

f(n) = a1*n + a0 종합해서 결론을 내리면 a1*n + a0 <= c*n이라는 조건이 만족해야 함을 알 수 있습니다.

 

마지막으로 "n>=n0" 에 대하여 를 해결해 보겠습니다. n0는 저희가 받을 변수입니다. 해당 변수보다 큰 값이 들어올 때

위에서 만들었던 식 a1*n + a0 <= c*n이 만족해야 O(n)의 정의를 만족시킬 수 있습니다.

이것을 알기 위해서는 부등식을 정리할 필요가 있습니다.

a1n - cn <= -a0 (편의를 위해 곱셈을 생략하겠습니다.)

kn <= -a0 (k = a1-c 일 때)

해당 식을 보면 k가 양수가 되면 n는 어떤 수에 대해 작을 때만 해당 식이 성립함을 볼 수 있습니다.

예를 들어 보겠습니다.

(a1 = 7, a0=7, c=6 일 때)

7n + 7 <= 6n라는 식을 만족해야 합니다.

식을 정리해 보면

7n - 6n <= -7

n <= -7 이 되고 n은 -7 이하의 수가 들어올 때만 해당 식이 성립됩니다.

하지만 문제에서는 n은 1~100까지 들어올 수 있고 n>=n0를 성립해야 한다고 조건을 두었습니다.

그렇다면 어떻게 하면 될까요? 

k가 음수가 되면 됩니다. 예를 들어 보겠습니다.

(a1 = 7, a0=7, c=8 일 때)

7n + 7 <= 8n

7n - 8n < -7

-n < -7

n > 7

n이 7보다 큰 수가 들어올 때 해당 수식이 성립하게 됩니다.

k가 음수인 경우 즉, a1-c가 음수일 때, c가 a1보다 커야 된다는 조건을 하나 넣어주면 됩니다.

 

 

그래서 정답 코드는 아래와 같습니다.

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a1 = sc.nextInt();
int a0 = sc.nextInt();
int c = sc.nextInt();
int n0 = sc.nextInt();
if(a1*n0+a0 <= (n0*c) && c>=a1){
System.out.println(1);
}else{
System.out.println(0);
}
}
}

정말 간단한 코드인데 수식을 찾아내기까지가 많이 어려웠습니다. 참고 견디다 보면 어느 정도 수준에 도달할 것이라고 믿습니다.