[백준] 24313번: 알고리즘 수업 - 점근적 표기 1 - JAVA

2024. 9. 20. 01:10·알고리즘

[작성일: 2023. 10. 10]

 

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

 

 

풀이

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();

        boolean bigO = true;

        for (int i = n0; i <= 100; i++) {
            if (a1 * i + a0 > c * i) {
                bigO = false;
                break;
            }
        }

        System.out.println(bigO ? 1 : 0);
    }
}

 

사실 이 문제는 아직도 이해가 잘 안 되는데 풀고나서 역으로 공부했다.

 

우선 f(n) = a1n + a0의 값을 c*n과 비교해야 한다. 만약 f(n)이 c*n보다 크거나 같다면 O(n) 정의를 만족하지 않는다. (f(n)이 c*n보다 항상 작거나 같다는 것을 의미한다.)

하지만 모든 n에 대해서는 검사할 필요가 없고, 문제에서 n >= n0인 경우메나 검사하면 된다고 했으므로 for문의 시작은 n0부터 100까지로 했다.

 

조건을 만족하지 않는다면 bigO 변수를 false로 설정하고 루프를 빠져나온다.

 

저작자표시 비영리 변경금지 (새창열림)
'알고리즘' 카테고리의 다른 글
  • [백준] 2231번: 분해합 - JAVA
  • [백준] 2798번: 블랙잭 - JAVA
  • [백준] 24262번~24265번: 알고리즘 수업 - 알고리즘의 수행 시간 - JAVA
  • [백준] 14215번: 세 막대 - JAVA
뚜비
뚜비
1년차 백엔드&iOS 개발자의 감자 탈출 블로그 🥔🥔
  • 뚜비
    뚜비의 개발로그
    뚜비
  • 전체
    오늘
    어제
  • 글쓰기     관리
    • Devlog
      • Back-End
        • Java
        • Spring
        • JPA
        • HTTP
        • Security
        • Back-End
        • Front-End
      • 알고리즘
      • iOS
        • Swift
      • Database
      • Tips
        • Git & GitHub
        • A to Z
      • 프로젝트
      • 생각정리
  • 태그

    spring
    김영한
    html
    자바스크립트
    MVC
    Java
    객체
    의존성주입
    백준
    Database
    생성자
    Swift
    성능최적화
    sql
    JPA
    DB
    jsp
    최주호
    데이터베이스
    Spring Security
    javascript
    프로그래머스
    Security
    알고리즘
    HTTP
    자바
    변수
    다형성
    게시판만들기
    스프링
  • hELLO· Designed By정상우.v4.10.0
뚜비
[백준] 24313번: 알고리즘 수업 - 점근적 표기 1 - JAVA
상단으로

티스토리툴바