F. Taming the Herd

- kir3i

문제에서 구하고자 하는 것은

주어진 로그를 토대로 추정할 수 있는 breakout의 최댓값, 최솟값을 출력하는 것입니다.

day1에는 반드시 breakout이 일어난다는 전제가 깔려있고,

로그가 잘못되었을 시에는 -1을 출력해야합니다.

풀이 방법은 다음과 같습니다.

1. barnlog 배열에 입력으로 주어진 log를 기록한다.

2. 앞에서부터 검사하며 주어진 기록을 토대로 하여 알 수 없 는 부분(-1)들을 채워나간다.

   2-1. 만약 0이 아닌 정수 k가 기록되어있다면 해당 인덱스 앞에는 무조건 0...k-1이 기록되어야만 한다. (만약 다른 정수가 저장되어있다면 잘못된 log)

   2-2. 만약 0이 저장되어있다면 그 이전의 값들은 알 수 없다.

3. barnlog를 완성할 수 있을만큼 했다면 먼저 0의 개수를 세준다. 이 값은 breakout 발생횟수의 최소치이다.

4. barnlog 내의 -1의 개수를 세준다. 3번의 결과와 4번의 결과의 합은 breakout 발생횟수의 최대치이다. -1은 모든 조건을 충족시켜서 log를 완성했음에도 여전히 알 수 없는 값이므로 모두 0이 될 수 있는 가능성이 있기 때문이다.

<C++>

#include <iostream>

using namespace std;

int barnlog[100];
int ans_m, ans_M;
int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int N;
    cin >> N;

    for(int i=0; i<N; i++)
        cin >> barnlog[i];

    //barnlog update
    barnlog[0] = 0;
    for(int i=1; i<N; i++)
    {
        if(barnlog[i] == -1)
            continue;

        //barnlog[i] > 0
        for(int j=1; j<=barnlog[i] && i-j>=0; j++)
        {
            if(barnlog[i-j] == -1)
                barnlog[i-j] = barnlog[i] - j;
            else if(barnlog[i-j] == barnlog[i] - j)
                continue;
            else
            {   //예상 외의 수가 있다.
                cout << -1;
                return 0;
            }
        }
    }
    //count
    for(int i=0; i<N; i++)
    {
        if(barnlog[i] == 0)
            ans_m++, ans_M++;
        else if(barnlog[i] == -1)
            ans_M++;
    }

    cout << ans_m << " " << ans_M;
}