[BOJ/JAVA] 27313번: 효율적인 애니메이션 감상

27313번: 효율적인 애니메이션 감상

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

키워드

애니메이션을 최대 $M$시간 동안만 보기로 했다.

한별이는 애니메이션을 동시에 최대 $K$개씩 묶어서 보기로 했는데, 한별이가 동시에 애니메이션을 보는 방법은 다음과 같다.

애니메이션을 보고 있지 않은 상태에서, 한별이는 아직 보지 않은 애니메이션 중  $K$개 이하의 애니메이션을 동시에 보기 시작한다.

애니메이션을 보고 있는 도중에는 새로운 애니메이션을 보기 시작할 수 없다. 이로 인해, 한별이는 보기 시작한 애니메이션 중에서 가장 긴 애니메이션이 끝날 때까지 다른 애니메이션을 보기 시작할 수 없다.

한별이는 애니메이션 시청의 달인이기 때문에 애니메이션이 끝남과 동시에 새로운 애니메이션을 보기 시작할 수 있다.

$N$개의 애니메이션 각각을 보는 데에 걸리는 시간이 주어질 때,  $M$시간 동안 볼 수 있는 애니메이션의 최대 개수를 구하시오.

---

구현

• 몇 개의 애니메이션을 볼 수 있는가를 매개변수로 탐색한다.

private static int solution()

• low
  • 볼 수 있는 애니메이션의 최소값 1

• high
  • 볼 수 있는 애니메이션의 최대값 N

low≤high 인 동안 반복

mid = (low+high);

mid개의 애니메이션을 볼 수 있는지 체크 canWatch()

1. 볼 수 있다면
   • 더 많은 애니메이션을 봐보기

2. 볼 수 없다면
   • 더 적은 애니메이션을 봐보기

private static boolean checkWatch(int goalAnimation)

goalAnimation의 수 만큼의 애니메이션을 볼 수 있는지 체크하는 메서드

그리디를 이용하여 체크한다.

시간이 오래걸리는 애니메이션(animations[goalAnimation-1])부터 최대 K개씩 묶어서 보기 시작한다.

만약 해당 시간이 M이하라면 볼 수 있고, 그렇지 않으면 볼 수 없다.

---

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;  public class java_27313 {     // 애니메이션이 N개     static int N;     // M시간동안 보기     static int M;     // K개씩 묶어서 보기     static int K;      static int animations[];      /*      * 보지 않은 애니메이션 중 K개 이하를 "동시에" 보기      * 새로운 애니메이션을 도중에 추가 불가      */     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));          StringTokenizer st = new StringTokenizer(br.readLine());         N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());         K = Integer.parseInt(st.nextToken());          // 애니메이션의 길이 목록         animations = new int[N];          st = new StringTokenizer(br.readLine());         for (int i = 0; i < N; i++) {             animations[i] = Integer.parseInt(st.nextToken());         }          // 정렬         Arrays.sort(animations);          /////////////////////////////////////////////         // 몇 개의 애니메이션을 볼 수 있는가? -> 매개변수         /////////////////////////////////////////////          int result = solution();          System.out.println(result);          br.close();     }      private static int solution() {         int low = 1;         int high = N;         int mid = -1;          while (low <= high) {             mid = (low + high) / 2;              // mid 개의 애니메이션을 볼 수 있는가?             boolean canWatch = checkWatch(mid);              // 볼 수 있다면.. 더 많은 애니메이션 봐보기             if (canWatch) {                 low = mid + 1;                 continue;             }              // 더 적은 애니메이션 봐보기             high = mid - 1;         }          return high;     }      // goalAnimation개의 애니메이션을 볼 수 있는가?     private static boolean checkWatch(int goalAnimation) {         // 볼 수 없다면..         if (animations[goalAnimation - 1] > M) {             return false;         }          // K개씩 나누어 적절하게 분배해보자         // 길이가 긴 것 부터 K개씩 나누어 보는 것이 이득이다.         long time = 0;          // [0,goalAnimation-1] 애니메이션을 봐야 함         int index = goalAnimation - 1;          while (true) {             // 시간 추가             time += animations[index];              // 음수라면..나머지 다 본 것임             if (index - K < 0) {                 break;             }              // K개 보기             index -= K;         }          return time <= M;     } }

---

Uploaded by N2T