백준 15753번 Taming the Herd

문제 링크입니다: https://www.acmicpc.net/problem/15753

문제에서 요구하는 바를 이해하는데 매우 오래 걸린 문제였습니다.

알고리즘은 아래와 같습니다.

1. 해당 카운터에 모순이 없는지를 확인합니다.

i) i번째에 적혀 있는 일 수가 (현재 - 마지막 탈출)보다 크거나

ii) (현재 - 적혀 있는 일)에는 탈출한 적이 없는 것이 확실하면 모순입니다.

2. 모순이 없다면 반복문을 돌면서 마지막 탈출 일 수를 표시하고 확실하게 탈출하지 않은 날들을 표시합니다.

3. 탈출한 날들의 합의 최소는 확실하게 탈출한 날만 셀 경우입니다.

4. 탈출한 날들의 합의 최대는 전체 일 수에서 확실하게 탈출하지 않은 날들을 제외한 경우입니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100;

 

int N;

int day[MAX];

bool isBreakout[MAX], notBreakout[MAX]; //확실히 탈출, 확실히 탈출 X

 

bool possible(void)

{

        int lastBreakout = 0;

        isBreakout[0] = true;

 

        for(int i=0; i<N; i++)

                 if (day[i] != -1)

                 {

                         //모순

                         if (day[i] > i - lastBreakout || notBreakout[i - day[i]])

                                 return false;

                         else

                         {

                                 lastBreakout = i - day[i];

                                 isBreakout[lastBreakout] = true;

                                 //마지막 탈출 이후 i번째 일까지 탈출 X

                                 for (int j = lastBreakout + 1; j <= i; j++)

                                          notBreakout[j] = true;

                         }

                 }

        return true;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> day[i];

 

        if (!possible())

                 cout << -1 << "\n";

        else

        {

                 int minimum = 0, maximum = 0;

                 for (int i = 0; i < N; i++)

                         if (isBreakout[i])

                                 minimum++;

                 for (int i = 0; i < N; i++)

                         if (!notBreakout[i])

                                 maximum++;

 

                 cout << minimum << " " << maximum << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~