📙[Algo] 24.02.03 알고리즘

알고리즘 문제) BOJ 13702. 이상한 술집

13702번: 이상한 술집

문제 요약

• 주전자 용량은 똑같지만 안에 있는 막걸리 용량은 랜덤
• N주전자를 주문하고 자신을 포함한 친구들 K명에게 막걸리를 똑같은 양으로 나눠주려고 함
  • 주전자끼리 섞지X
    • 남는 건 버림
• K명에게 최대한 많은 양의 막거리를 분배할 수 있는 용량 ml는?

시간 제한

• 1초

입력

• 주전자 개수 N, 사람 수 K
  • N은 10000이하 정수
  • K는 100만 이하 정수
  • N≤K
• N개의 줄에 주전자 용량이 주어짐
  • 막걸리 용량은 2^31-1이하 자연수 또는 0

출력

• k명에게 나눠줄 수 있는 최대 막걸리 용량 ml?

접근법

1. 완전 탐색
   • 막걸리 용량 최댓값부터 하나씩 감소하면서 K명에게 분배할 수 있는 체크
   • 용량이 최대 2^31-1까지 가능하기 때문에 시간초과가 뜰 수 있다.
2. 최적화 하기
   • 중간값부터 체크를 시작한다.
   • 예를들어, k=11, 427, 541, 774, 822가 주어진다면
     
     • s=1, e=822, mid=411
       • 411씩 분배하고 나면
         • 16, 130, 363, 0이 남으며, 5명까지만 분배 가능하다
         • 용량을 줄여야 하므로 e = mid-1
     • s=1, e=410, mid=205
       • 205씩 분배하고 나면
         • 17, 2, 159, 412가 남고, 11명까지 충분히 분배 가능
         • 용량을 조금 늘려도 될 것 같으므로 s = mid+1
     • s=206, e=410, mid= 308
       • 308씩 분배하면 11명까지 분배 X
       • 용량 줄여야 하므로 e=mid-1,,,
     ⇒ 이렇게 계속 진행!!!(가능할 때 최댓값 갱신)

코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, K;
    static int[] arr;
    static long answer = 0;

    static void binarySearch(long s, long e) {

        long mid;
        int cnt;
        while (s <= e) {
            mid = (s + e) / 2;

            cnt = 0;

            if (mid == 0) {
                cnt = K;
            } else {
                for (int i = 0; i < N; i++) {
                    cnt += arr[i] / mid;
                }
            }

            if (cnt >= K) {
                s = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                e = mid - 1;
            }

        }

    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        binarySearch(0, max);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2805. 나무 자르기

2805번: 나무 자르기

문제 요약

• 나무 M미터가 필요
• 절단기 높이 H 지정
• 그다음 한 번에 나무들을 절단
• 필요한 만큼만 가져가고 싶을 때 최소 M미터의 나무를 가져가기 위해 절단기에 설정할 수 있는 높이 최댓값은?

시간 제한

• 1초

입력

• 나무의 수 N, 집으로 가져가려는 나무 길이 M
  • 1≤N≤100만
  • 1≤M≤20억
• 나무의 높이
  • 10억 이하의 양수 또는 0

출력

• 최소 M미터 나무를 가져가기 위해 설정할 수 있는 절단기 높이 최댓값?

접근법

1. • 완전 탐색으로 생각하기
     • 모든 높이에서 잘라보고 가능한 경우마다 높이 최대값 갱신 나무높이가 10억까지 가능하고, 100만개 나무까지 존재할 수 있기 때문에 10억*100만 시간이 걸린다.
   • 최적화
     • 이진탐색으로 최대높이~0의 중간점부터 탐색한다. 충분하면 s=mid+1, 부족하면 e=mid-1로 이동하며 탐색.

코드

import java.io.*;
import java.util.*;


public class Main {
    static int N, M;
    static int[] arr;
    static int answer = 0;

    static void binarySearch(int s, int e) {

        int mid;
        long sum;
        while (s <= e) {
            mid = (s + e) / 2;

            sum = 0;
            for (int i = 0; i < N; i++) {
                if(arr[i] >= mid) sum += arr[i] - mid;
            }

            if (sum < M) {
                e = mid - 1;
            } else {
                s = mid + 1;
                answer = Math.max(answer, mid);
            }
        }

    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }

        binarySearch(0, max);


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}