문제
오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
이 정의는 실제 O-표기법링크텍스트과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.
입력
첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)
출력
f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.
예제
문제를 자세히 보면 결론적으로
f(n) = a1*n + a0
이면서 n은 n0보다 무조건 크거나 같기 때문에 아래와같이 정리할 수 있습니다.
a1*n0 + a0 <= c * n0이 조건을 만족하면 "1" 을 출력하고 성립이 안된다면 "0"을 출력하면 됩니다.
이것을 저는 처음에 이렇게 구현했습니다.
public class B_24267 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a1 = Integer.parseInt(st.nextToken());
int a0 = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(br.readLine());
int n0 = Integer.parseInt(br.readLine());
if(a1*n0 + a0<= c * n0) {
System.out.println("1");
}else {
System.out.println("0");
}
}
}
결과
예제안에 입력값들은 모두 정상적으로 나왔지만 88%에서 오답이 나왔고 반례를 찾아보았습니다.
a0이 음수인경우 같은 조건에서 서로다른 결과가 나올수 있다.
예를들어 a1 = 5 , a0 = -4 , c = 3 , n0 = 1 인경우
5n - 4 ≤ 3n (n ≥ 1) 이라는 식이 나오며, n 은 n0보다 항상 크거나 같기 때문에 n을 1씩늘려 계산해보면
(n = 1)
1 ≤ 3 (true)
(n = 2)
6 ≤ 6 (true)
(n = 3)
11 ≤ 9 (false)
a0이 음수 일경우 a1*n0 + a0 <= c * n0 에서 조건에 "참"과 "거짓"이 모두 나오기 때문에 조건을 하나 더 걸어야합니다.
a1*n0 + a0<= c * n0 && a1 <= c 조건을 넣는다면 a0이 음수여도 항상 조건이 성립이 됩니다.
정답 코드
public class B_24267 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a1 = Integer.parseInt(st.nextToken());
int a0 = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(br.readLine());
int n0 = Integer.parseInt(br.readLine());
if(a1*n0 + a0<= c * n0 && a1 <= c) {
System.out.println("1");
}else {
System.out.println("0");
}
}