[JAVA] 백준 이진탐색 - 실버모음3(2512 예산, 2343 기타 레슨, 2792 보석 상자)

 

어느정도 이진탐색 기본기를 다진 것 같으니 활용을 열심히 해보자!

 

 

 

2512 예산 - 실버2

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

2512번: 예산

 

• 처음부터 배정이 가능한 경우 -> 예산의 최댓값 출력
• 배정 불가능 경우 -> 상한액 출력
• 그냥 상한액을 이진탐색으로 찾는다고 생각하면 되겠다
  • 배정이 가능하면 오른쪽을 탐색, 배정이 불가능하면 왼쪽 탐색
  • [가능, 가능, 가능, 불가능, 불가능, ...] 이런식으로 나올 것이니 upperbound값을 구하여 -1을 해주면 될듯

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int provinceCnt = Integer.parseInt(br.readLine());
    int[] budgets = new int[provinceCnt];

    StringTokenizer st= new StringTokenizer(br.readLine());
    int maxBudget = -1;
    for (int i =0; i<provinceCnt; i++) {
      int b = Integer.parseInt(st.nextToken());
      budgets[i] = b;
      if (b > maxBudget)
        maxBudget = b;
    }

    int totalBudget = Integer.parseInt(br.readLine());

    Arrays.sort(budgets);

    long startBudget = 0;
    long endBudget = maxBudget+1;
    while (startBudget < endBudget) {
      long midBudget = (startBudget + endBudget)/2;

      //upperbound
      if (canDistribute(midBudget, budgets, totalBudget))
        startBudget = midBudget+1;
      else
        endBudget = midBudget;
    }
    
    System.out.println(startBudget-1);
  }

  private static boolean canDistribute(long midBudget, int[] budgets, int totalBugdet) {
    long sum = 0;
    for (int b: budgets) {
      if (b >= midBudget)
        sum += midBudget;
      else
        sum += b;
    }

    if (sum <= totalBugdet)
      return true;
    else
      return false;
  }
}

• 예산들을 budget 배열에 받는다
  • 받으면서 예산의 최댓값을 저장한다
• 예산들을 오름차순으로 정렬한다(이진탐색을 위한 정렬)
• startBudget을 0으로, endBudget을 (max값+1) 로 시작하여 이진탐색을 수행한다
  • 이진탐색은 상한선을 찾기위한 탐색이다 -> 최대 max값, 최소 0이 될 수 있음
  • 해당 상한선으로 분배했을 때 총 예산이 넘지 않는지 확인한다
  • 만약 넘으면 왼쪽을 탐색하고, 같거나 넘지 않으면 오른쪽을 탐색한다 (upperbound)
• 이진탐색을 끝낸 후 startBuget은 upperbound값을 가리킬 것이다
  • [분배가능, 분배가능, 분배불가능, ... ] 중 분배가능 마자막의 바로 다음 인덱스의 분배불가능 가리킴
  • upperbound-1 값이 최대예산상한액이다.

 

 

 

2343 기타레슨 - 실버1

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

2343번: 기타 레슨

 

• 블루레이의 크기의 범위는 (강의의 최대크기 ~ 모든 강의의 합)이다
  • 블루레이 하나에 모든 강의를 다 넣을 수 있음
• 이 범위 안에서 가장 최소의 크기를 구하면 된다
• 범위를 돌아다니면서 M개의  블루레이에 강의를 모두 넣을 수 있는지 확인하고, 되는 범위 중 최소를 구하면 되겠다
  • 블루레이 크기는 다음과 같이 나올거다 [불가능, 불가능, 가능, 가능, 가능, ...]
  • 이진탐색을 사용하는 게 좋을 것 같고, 
  • 최소의 크기는 lowerbound를 구해주면 되겠다!

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());

    int lectureCnt = Integer.parseInt(st.nextToken());
    int bluelayCnt = Integer.parseInt(st.nextToken());

    int[] lecture = new int[lectureCnt];
    int maxLectureLen = 0;
    int lectureSum = 0;

    st = new StringTokenizer(br.readLine());
    for (int i =0; i<lectureCnt; i++) {
      int lec = Integer.parseInt(st.nextToken());
      lecture[i] = lec;
      lectureSum += lec;
      if (lec > maxLectureLen)
        maxLectureLen = lec;
    }

    int startSize = maxLectureLen;
    int endSize = lectureSum+1;

    while (startSize < endSize) {
      int mid = (startSize + endSize)/2;

      if (canInput(mid, bluelayCnt, lecture))
        endSize = mid;
      else
        startSize = mid+1;
    }

    System.out.println(startSize);
  }

  private static boolean canInput(int mid, int bluelayCnt, int[] lecture) {
    int cnt = 0;
    int sum = 0;
    for (int len: lecture) {
       if (sum+len <= mid) {
         sum += len;
       } else {
         cnt ++;
         sum = len;

         if (cnt > bluelayCnt)
           return false;
       }
    }

    if (sum != 0)
      cnt ++;

    if (cnt <= bluelayCnt)
      return true;
    else
      return false;
  }
}

• 강의 길이를 lecture배열에 받으면서
  • 강의 길이의 최댓값을 maxLectureLen에 저장하고
  • 강의 길이의 총 합을 lectureSum에 저장한다
• 최대 강의 길이를 start로, 강의길이의 총 합 + 1을 end로 잡고 "블루레이 길이"에 대한 이진탐색을 수행한다
  • lowerbound를 구해줄 것이므로
  • 강의가 해당 길이의 블루레이에 강의들이 모두 들어갈 수 있다면 왼쪽으로 보낸다
  • 들어갈 수 없다면 오른쪽으로 보낸다
• 넣을 수 있는지 여부는 직접 다 넣어보면서 구했다

 

 

2792 보석 상자 - 실버1

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

2792번: 보석 상자

 

• 한 아이는 같은 색의 보석만 가질 수 있고, 못받는 아이가 있을 수 있다
• 보석은 모두 나눠줘야하는데
• 한 아이가 가진 최대 보석개수가 최소가 되도록 나눠줘야함
• 아이들 수가 색상 수보다 많기 때문에 각 아이가 색상 하나씩 모두 가지는 게 최대 질투심일거고
• 잘 나눠지면 1개이상의 개수로 적어질 수 있다

 

• 최대 보석 개수를 기준으로 이진탐색 수행
• start는 1로 하고, end는 서로 다른 색 보석들 중 보석 개수의 최댓값
• 형태는 [불가능, 불가능, 가능, 가능, ...] 이런 식으로 나올 것임 -> 최대보석 개수의 최솟값을 구해야하니까 lowerbound를 구하면 되겠다!

 

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st= new StringTokenizer(br.readLine());

    int childrenCnt = Integer.parseInt(st.nextToken()); //10억
    int colorCnt = Integer.parseInt(st.nextToken()); //10억 가능
    int[] color = new int[colorCnt];
    int maxJewel = 0;

    for (int i =0; i<colorCnt; i++) {
      int jewel = Integer.parseInt(br.readLine());
      color[i] = jewel;
      if (maxJewel < jewel)
        maxJewel = jewel;
    }

    int start = 1;
    int end = maxJewel+1;

    while (start < end) {
      int mid = (start + end)/2;  //보석 개수 상한선

      if (canDistribute(mid, childrenCnt, color))
        end = mid;
      else
        start = mid+1;
    }

    System.out.println(start);
  }

  private static boolean canDistribute(int mid, int childrenCnt, int[] color) {
    long cnt = 0;

    for (int c: color) {
      cnt += (c/mid);
      if (c%mid != 0)
        cnt ++;

      if (cnt > childrenCnt)
        return false;
    }

    return true;
  }
}

 

 

 

 

 

이제 골드문제를 풀어봐야겠다!