[3186번] 소변기

문제 출처 :

https://www.acmicpc.net/problem/3186

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

알고리즘 분류로는 '유한 상태 오토마타'라고 되어있다.

결국 구현이 중요한 문제이다.

arr[i] 값이 1이라면 소변을 보고 있는 중이고, 그것이 k 이상이 되면 소변기는 '사용중'으로 표시시켜준다.

이때 소변기의 물내림 시간은 당연히 0으로 해주어야 한다.(소변을 보는 중이니 물 내림 카운트는 0임이 명백하다.)

만약 arr[i]값이 0이라면 이때 사용중이었다면 flushTime를 ++해준다. 이때 l 이상값이 된다면 소변기를 flush해준다. 그리고 flushTime를 0으로 바꿔주고 useTime또한 0으로 바꿔준다.(소변기에 사람이 없다면 useTime는 0임이 명백하다.)

이때 flush가 한번도 true.가 되지 않았다면 NIKAD이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <iostream> #include <cstdio>   using namespace std;   bool arr[10002];   int main() {     int k, l, n;     scanf("%d %d %d", &k, &l, &n);       for (int i = 1; i <= n; i++)         scanf("%1d", &arr[i]);       bool use = false;     int useTime = 0;     bool flush = false;     int flushTime = 0;       for (int i = 1; i <= n; i++)     {         if (arr[i])         {             useTime++;             if (useTime >= k)                 use = true;             flushTime = 0;         }           else         {             if (use)             {                 flushTime++;                 if (flushTime >= l)                 {                     printf("%d\n", i);                     flush = true;                     use = false;                       flushTime = 0;                 }             }               useTime = 0;         }     }       if (use)     {         printf("%d\n", l + n - flushTime);         flush = true;     }       if (!flush)         printf("NIKAD\n");       return 0; }ntf("%d\n", maxVal);     printf("%d\n", minVal);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus