백준 33678 로마의 휴일 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/33678

• N일 중 휴가를 딱 한 번만 연속된 기간으로 갈 수 있음

• 휴가에서 돈을 쓰려면 근무 일자에 돈을 K원 이상 벌어야 함.

• 휴가 가기 전에는 일자 급여 * X 원 만큼 더 벌 수 있고, 휴가지에 쓴 돈은 후불도 되기 때문에 휴가 가기전, 갔다 온 후에 벌었던 일급의 합이 K원 이상이기만 하면 됨.

• 최대한 휴가를 오랫동안 보내고 싶음.

(1) 조건 분석 📊

1. 휴가 일자의 최대값이 200,000 이므로 휴가일자를 이중 반복문으로 계산해서는 안된다.

2. 코드가 나오기까지 🛠️

(1) 핵심 원리

1. K원 이상 벌었음 → 휴가 일수 더 늘려도 됨, 이분탐색의 mid 값 상향 조정

2. K원보다 못 벌었음 → 휴가 일수 줄여야함. 이분탐색의 mid 값 하향 조정

(2) 부분합 활용

1. N일 중 특정 S 길이의 구간을 휴가로 선정

2. 그 휴가 기간 전 후로 급여 계산

• 부분합의 i일자
  : i일까지 보너스없이 번 최대 금액

• 부부합 i일자 - 부분합 j 일자 (j <= i)
  : j+1 ~ i일까지의 급여 누적합

(3) 시간복잡도 분석 ⏳

• 이분 탐색 O(logN)

• 이분 탐색 한 번 할 때마다 K원 넘어 버는지 확인 O(N)

3. 코드 🌐

import java.util.*;
    import java.io.*;
import java.util.Map.Entry;
import java.util.function.Supplier;

// b 33678 로마의 휴일
public class Main {
    static int N, K, X;
    static int [] pays;
    static int [] sums;
    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());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        pays = new int [N+1];
        sums = new int [N+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < N+1; i++){
            pays[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = 1; i < N+1; i++){
            sums[i] = sums[i-1] + pays[i];
        }
        int answer = binary_search();
        System.out.println(answer == 0? -1 : answer);
    }

    public static int binary_search(){
        int start = 0;
        int end = 200_000;
        while (start <= end){
            int mid = (start+end)/2;
            if(isDeal(mid)) start = mid+1; // mid 일 휴식으로도 K금 벌 수 있으면 쉬는 날 늘리기
            else end = mid-1; // 안되면 쉬는 날 줄이기
        }
        return end;
    }

    public static boolean isDeal(int vacation) {
        for(int start = 1; start <= N - vacation + 1; start++){
            long pay = 0L;
            pay += (sums[start-1])*(long)X;
            pay += (sums[N] - sums[start+vacation-1]);
            if(pay >= K) return true;
        }
        return false;
    }
}