[소프티어] [21년 재직자 대회 본선] 코딩 테스트 세트 - JAVA

in Algorithm on 그리디 알고리즘

https://softeer.ai/practice/info.do?idx=1&eid=630

풀이

난이도별로 문제의 개수가 주어지고, 이 문제들을 난이도별로 하나씩 배치할때 최대 몇개의 세트가 나올 수 있는지 구하는 문제이다.

난이도는 1부터 N까지 있고, i레벨 또는 i+1레벨로 할 수 있는 문제가 있다.

각각 c와 d배열에 나누어 저장했다.

d배열의 값들을 c에 적절히 옮겨야 한다.

최댓값은 c[N]에 d[N-1]을 모두 옮겼을 때이다. 따라서 (0, c[N] + d[N-1])의 범위로 이분탐색을 통해 해당 값이 될 수 있는지 검사했다.

이분탐색으로 풀어야겠다고 생각을 못했던 문제였다.

최종 값을 이분탐색으로 찾아 체크하는 방식으로 풀 수 있구나 알게된 문제였다.

메모리: 38.74MB

시간: 380ms

언어: Java 11

코드

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

public class Main {

    static int N;
    static long[] c, d;
    static long ans;

    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());
        int T = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            c = new long[N];
            d = new long[N - 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N * 2 - 1; i++) {
                if (i % 2 == 0) {
                    c[i / 2] = Long.parseLong(st.nextToken());
                } else {
                    d[i / 2] = Long.parseLong(st.nextToken());
                }
            }
            ans = 0;
            binarySearch(0, d[N - 2] + c[N - 1]);

            sb.append(ans).append("\n");
        }

        System.out.println(sb);

    }

    private static void binarySearch(long left, long right) {
        long mid = (left + right) / 2;
        long pass = 0;
        boolean success = true;
        for (int i = 0; i < N - 1; i++) {
            long mass = c[i] + pass;
            if (mass >= mid) {
                pass = d[i];
                continue;
            } else {
                mass += d[i];
                pass = mass - mid;
            }

            if (mass < mid) {
                success = false;
                break;
            }
        }

        if (c[N - 1] + pass < mid) {
            success = false;
        }

        if (success) {
            ans = mid;
            if (left <= right) {
                binarySearch(mid + 1, right);
            }
        } else {
            binarySearch(left, mid - 1);
        }
    }

}