동혁이가 깔아놓은 게임에 바이러스가 침투했다.

게임을 실행하려고 하자, 이상한 문자열 s, 어떤 계좌번호와 함께 게임 대신 다음과 같은 문구가 떴다.

s에 있는 1(0…0)1 패턴을 모두 세서 그 개수를 아래에 써 넣거나, 나에게 10만원을 송금해라. 그래야만 게임을 계속 할 수 있을 것이다. 1시간 내에 두 가지를 모두 못한다면, 앞으로 영원히 그 게임을 할 수 없을 것이다.

여기서 1(0…0)1 패턴에서 (0…0)이란 하나 이상의 0이 연속된 것을 말한다. 예를 들어 101이나 10001 같은 것이다. s가 jun1001011gol이라면, 1(00)1과 1(0)1 이 보이므로 패턴의 개수는 2이다.

게임은 해야겠고, 저런 삼류 해커에게 돈을 지불할 수는 없다. 어떤 s가 주어지더라도 패턴의 개수를 재빠르게 세주는 프로그램을 작성하자.

패턴 세기 timer 1s memory 64MB

패턴 세기 1s 64MB