공부 215일차: 백준 24313번 알고리즘 수업 - 점근적 표기 1 자바 java

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

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

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

 

 

 

---

백준 24313번 문제 알고리즘 수업 - 점근적 표기 1

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	1402	454	389	32.634%

문제

오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

O(g(n)) = {f(n) | 모든 n ≥ n₀에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n₀가 존재한다}

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 f(n) = a₁n + a₀, 양의 정수 c, n₀가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

입력

첫째 줄에 함수 f(n)을 나타내는 정수 a₁, a₀가 주어진다. (0 ≤ |a_i| ≤ 100)

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n₀가 주어진다. (1 ≤ n₀ ≤ 100)

출력

f(n), c, n₀가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.

제한

 

예제 입력 1

7 7
8
1

예제 출력 1

0

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

예제 입력 2

7 7
8
10

예제 출력 2

1

f(n) = 7n + 7, g(n) = n, c = 8, n₀ = 10이다. 모든 n ≥ 10에 대하여 7n + 7 ≤ 8n 이므로 O(n) 정의를 만족한다.

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/371

시간 복잡도에 대해 정리해둔 포스팅

 

이 문제는 두 가지 방식으로 생각해볼 수 있다

 

1. 브루트 포스처럼 for문을 사용하여 모든 경우를 다 계산해보기

 

문제에서 요구하는 게

// f(n) <= c * g(n)
a1*n + a0 <= c*n

라는 조건을 만족하면 되는 것이므로 아래와 같이 그대로 반복문을 돌린다 (모든 경우의 수를 확인해보는 것)

for(int n = n0; n < 101; n++) {
    if(a1*n + a0 > c*n) {
        answer = 0;
        break;
    }
}

만족하지 않으면 0으로 answer값을 바꾸고, 즉시 반복문을 탈출하면 된다

 

 

2. 공식으로 간단하게 표현하기

 

(a1 * n0 + a0 <= c * n0) || (c >= a1) -> 조건 만족 => 1
(a1 * n0 + a0 > c * n0) || (c < a1) -> 조건 불만족 => 0

 

 

 

---

정답 인정 코드

---

 

1) 풀어쓰기(for문)

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int answer = 1;
        int a1 = Integer.parseInt(st.nextToken());
        int a0 = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(br.readLine());
        int n0 = Integer.parseInt(br.readLine());
 
        for(int n = n0; n < 101; n++) {
            if(a1*n + a0 > c*n) {
                answer = 0;
                break;
            }
        }
        
        bw.write(answer+"");
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

2) 공식 사용

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int answer = 1;
        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) || (c < a1)) {
            answer = 0;
        }
        
        bw.write(answer+"");
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

 

 

---

그때 공식을 사용하는 게 효율적이라는 걸 깨달았기 때문에 공식을 어떻게 도출할지 생각해본 뒤 답안을 제출했다