[BOJ] 24887 : 최대한의 휴식

문제 링크

24887번: 최대한의 휴식 (acmicpc.net)

24887번: 최대한의 휴식

숭고한 대회 DIvision2 E번 문제.

대회 당일엔 앞에서 막히는 바람에 읽어보지도 못했다 ㅎㅎ;

풀이

연속으로 쉰 날의 최소값의 최대값을 구하는 문제다. 연속으로 쉬는날의 최소값을 이분탐색으로 찾아준다.

초기 범위는 Left = 0, Right = N 으로 설정해줬다.

DP배열을 선언해서 DP[i] 연속으로 쉬는날의 최소가 mid 일때, i번째 날까지 채울수 있는 할당량의 최대값을 저장해두 었다. 그래서 DP[N] 까지 구해준뒤 DP[N] >= M(할당량) 이면 mid가 유효한 것이다.

if(DP[N] >= M)
	L = mid + 1;
else R = mid - 1;

상황을 가정해보자. 현재 mid 값이 3이라는 것은 연속으로 쉴 수 있는 날의 최소값이 3일이라는 뜻이다.

현재 i = 5 이다 DP[5] 를 채우고 있다. 5번째 날에는 일을 할 수도 있고 안할 수도 있다.

그렇기 때문에 2가지 경우를 비교해야한다.

1. 만약 일을 한다면, 최소 3일은 쉬어야하기 때문에  4일 전인 첫번째날까지 채울 수 있는 최대 할당량 + 5번째 날 채울 수 있는 할당량.

2. 만약 일을 안한다면 바로 전날까지 채울 수 있는 할당량의 최대인 DP[4] 를 그대로 가져온다.

DP[5] = max(DP[4], Work[5] + DP[1]) 이 되어야한다.

즉, DP[i - 1]과 DP[i - mid - 1]을 비교해서 더 큰 값을 DP[i]에 저장한다.

물론 i - mid - 1이 0보다 작아지는 경우에는 예외다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, pair<pair<int, int>, bool>>, vector<pair<pair<int, int>, pair<pair<int, int>, bool>>>, greater<pair<pair<int, int>, pair<pair<int, int>, bool>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 200000 + 5;
int N, M;
int W[MAX_N];
ll DP[MAX_N];
 
int Binary_search(int L, int R) {
    int ans = 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        for (int i = 1; i <= N; i++) {
            DP[i] = W[i];
            DP[i] = max(DP[i], DP[i-1]);
            if (i > mid)
                DP[i] = max(DP[i], (ll)W[i] + DP[i - mid - 1]);
        }
        if (DP[N] >= M) {
            ans = max(ans, mid);
            L = mid + 1;
            continue;
        }
        else {
            R = mid - 1;
        }
    }
    return ans;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    ll sum = 0;
    int Max = 0;
    for (int i = 1; i <= N; i++) {
        cin >> W[i];
        sum += W[i];
        Max = max(Max, W[i]);
    }
    if (Max >= M) {
        cout << "Free!\n";
        return 0;
    }
    else if (sum < M) {
        cout << -1 << "\n";
        return 0;
    }
    cout << Binary_search(0, N) << "\n";
    return 0;
}

이번에도 범위를 잘 생각하지 못하고 long long이 아닌 int로 선언해서 계속 틀렸습니다를 받았다. 그렇다고 매번 long long으로 선언할 수도 없다. 언제쯤 long long 인걸 바로 인지할 수 있을까.