[BOJ] 24453 : 디버깅

문제 링크

24453번: 디버깅 (acmicpc.net)

24453번: 디버깅

인규가 Y개 이상의 오류를 제거한 후 에디터가 제거해야 할 오류의 수의 최대값을 구하는 문제.

풀이

먼저 경우의 수를 나누어 보자.

1. 인규가 아무런 오류를 수정하지 않아도 에디터가 자동으로 오류를 수정해 줄 수 있는 경우

즉, 최초 입력에서 부터 이미 오류가 없는 연속된 코드의 줄의 수가 X이상인 상태.

이런 경우는 인규가 최소 Y개의 오류는 수정해야하므로 아무 오류 Y개를 수정한다.

그럼 에디터는 최대 M - Y 개를 해결해야한다. 

2. 인규가 Y개 이하의 오류만 수정해주면 에디터가 자동으로 오류를 수정해 줄 수 있는 경우

인규가 Y이하 개의 오류만 수정해주면 오류 없는 연속된 코드 줄의 수가 X이상이 되는 경우이다

이런 경우 역시 에디터는 최대 M - Y개의 오류를 해결해야한다. 

3. 인규가 Y개를 초과해서 오류를 수정해야만 에디터가 해결해 줄 수 있는 경우

이 경우 에디터가 최대 (M - 인규가 이미 해결한 오류의 수) 만큼의 오류를 해결해야한다.

즉, 인규가 Y개를 초과해 오류를 수정해야하는데 그 중에서도 최대한 적게 오류를 수정해야한다.

1번의 경우에는 입력을 받은 후에 바로 판별해주었다. 주어진 두 오류 사이의 간격을 계산해

그 중에 최대 길이를 찾아서 판별해주면 된다.

 

1번의 경우가 아니라면 인규가 반드시 손을 대야하는 경우에 최소 몇 개의 오류를 해결해야

이후엔 에디터가 자동으로 해결해줄지를 계산해야한다. 오류없는 연속된 코드 줄 수가 X줄만 있으면 된다.

X가 3이라고 가정하자

1~3, 4~6, 7~9 ... N-2 ~ N 으로 범위를 나누어서 범위안의 오류 개수 중 최소를 찾으면 된다.

그렇게 코드를 작성해보면

#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 <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int INF = INT_MAX;
const int MAX_N = 20000000 + 5;
int N, M, X, Y;
bool Error[MAX_N];
vector<int> Error_num;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int MAX_gap = 0;
    for (int i = 0; i < M; i++) {
        int a; cin >> a;
        Error[a] = true;
        Error_num.push_back(a);
        if (!i) MAX_gap = max(a - 1, MAX_gap);
        else MAX_gap = max(MAX_gap, a - (Error_num[i - 1] + 1));
        if (i == M - 1) {
            MAX_gap = max(MAX_gap, N - a);
        }
    }
    cin >> X >> Y;
    if (MAX_gap >= X) {
        cout << M - Y << "\n";
        return 0;
    }
    int cnt = 0;
    for (int j = 1; j < 1 + X; j++) {
        if (Error[j])
            cnt++;
    }
    int Min_Error = cnt;
    for (int i = 2; i <= N - X + 1; i++) {
        if (Error[i - 1])
            cnt--;
        if (Error[i + X - 1])
            cnt++;
        Min_Error = min(cnt, Min_Error);
        if (Min_Error < Y)
            break;
    }
    if (Min_Error < Y)
        cout << M - Y << "\n";
    else cout << M - Min_Error << "\n";
    return 0;
}

여기서 범위내의 에러 수를 찾을 때

매번 반복문을 돌면서 개수를 세면 시간제한이 0.6초밖에 안돼서 시간초과가 난다.

1~3 까지는 반복문으로 개수를 세주고 cnt 변수에 저장한다.

다음 2~4 까지 셀때는 앞서 1~3 범위와 2,3이 겹친다.

그래서 1번줄에 에러가 있었다면 일단 cnt-1을 해주고 4번줄에 에러가 있다면 cnt+1을 해주면된다.

그럼 매번 반복문을 돌지않고도 범위 내 오류의 수를 계산할 수 있다.