developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테자바준비
  • BOJ파이썬풀이
  • 코테파이썬
  • 카카오코테
  • 삼성코테파이썬준비
  • 삼성코테기출
  • 카카오코테java풀이
  • Arima
  • 통계학
  • 삼성코테파이썬풀이
  • SW역량테스트파이썬
  • MA모형
  • 삼성코테구현풀이
  • 삼성코테자바풀이
  • 삼성코테기출자바풀이
  • SW역량테스트파이썬풀이
  • 시계열
  • c++ 빌더 패턴
  • 시계열분석
  • c++디자인패턴
  • 삼성코테준비
  • ARIMA모형
  • 삼성코테자바꿀팁
  • 데이터분석
  • AR모형
  • 운영체제인터럽트
  • 삼성코테구현문제추천
  • 삼성코테파이썬
  • 백준파이썬풀이
  • 통계분석

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 입국심사 3079번 (JAVA)

2022. 2. 21. 23:04

❓ 문제 - 백준 입국심사 3079번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/3079)

 

3079번: 입국심사

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 이진탐색(Binary Search)로 해결했다.

  • 이진 탐색 -> 시간을 중심으로 탐색
  • 해당 시간일 때 최대 몇 명의 사람을 입국 심사대에서 통과 시킬 수 있는가를 중점으로 이진탐색을 진행
  • 만약 mid초일 때, m명 이상의 사람을 해당 시간에 입국 심사대에서 보낼 수 있음 -> 시간 탐색범위를 0 ~ mid-1
  • 만약 mid초 일 때, m-1 이하의 사람을 해당 시간에 입국 심사대에서 보낼 수 있음 -> 시간 탐색 범위를 mid+1 ~right
  • 처음 left는 0으로 설정, right는 각 입국심사대에서 걸리는 시간의 최대값(Tk) * 심사 받으려는 사람의 수(M)

2. 느낀점

  • 일단... 탐색의 중심을 뭘로 잡느냐가 이 문제의 핵심인듯...
  • 그리고 주어진 데이터의 범위가 말도 안되고 최적 조건을 찾는다 ? 그럼 바로 이진탐색을 떠올려보기..
  • 이진탐색시 데이터 범위가 엄청 크므로 데이터 타입의 범위를 조심해서 변수타입을 지정하기...!

 

💻 소스코드

// BOJ - 입국심사(3079번)
// BinarySearch
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class BinarySearch_BOJ_3079 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N과 M 그리고 각 입국 심사대에서 걸리는 시간을 arr 배열에 데이터를 입력받음
        String[] data = br.readLine().split(" ");
        int n = Integer.parseInt(data[0]);
        int m = Integer.parseInt(data[1]);
        int[] arr = new int[n];
        // 그리고 가장 입국 심사대에서 오래 걸리는 시간을 max_value 로 구함
        int max_value = 0;
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
            max_value = Math.max(max_value, arr[i]);
        }
      
        long left = 0L;
        long right = (max_value) * 1000000000L;

        long ans = 0L;
        while (left<= right){
            long mid = (left+right) / 2;
            // mid초 일 때 각 입국 심사대에서 보낼 수 있는 수를 카운트 해줌
            long cnt = 0;
            for(int i=0;i<n;i++){
                cnt += (mid / arr[i]);

            }
            // 비교 후 탐색 범위 변경
            if(cnt >= m){
                ans = mid;
                right = mid-1;
            }  else if (cnt < m){
                left = mid +1;

            }
        }

        System.out.println(ans);

    }
}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 주사위 굴리기2 23288번 (JAVA)  (0) 2022.03.04
BOJ - 마법사 상어와 복제 23290번 (JAVA)  (0) 2022.03.01
BOJ - 빙산 2573번 (JAVA)  (0) 2022.02.19
SW Expert Academy - 무선 충전 (JAVA)  (0) 2022.02.17
BOJ - 전구와 스위치 2138번 (JAVA)  (0) 2022.02.16
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 주사위 굴리기2 23288번 (JAVA)
    • BOJ - 마법사 상어와 복제 23290번 (JAVA)
    • BOJ - 빙산 2573번 (JAVA)
    • SW Expert Academy - 무선 충전 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바