Informatica Online Judge

  잠수함 식별 [0358 / 0166]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 179   Total Tried : 1212


The Champion of this Problem (C++) : gs18040 - ms / 206byte
My Best Submission (C++) : N/A

[]

Background

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함 종류에 따라서 다르다고 한다. 우리는 물 속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다.이 문제에서는 잠수함의 소리가 두 종류의 단위소리의 연속으로 이루어져 있고,그 단위 소리를 각각 0 과 1 로 표시한다.

또, 한 특정한 소리의 반복은 ~로 표시한다. 예를 들어 x~ 는 x 과 한번 이상 반복되는 모든 소리의 집합을 말하고,(xyz)~ 는 괄호안에 있는 xyz 로 표현된 소리가 한 번이상 반복되는 모든 소리의 집합을 말한다.
다음의 예를 보자.

1~={1,11,111,...}
(01)~={01,0101,010101,...}
(1001)~={1001,10011001,100110011001,...}
10~11={1011,10011,100011,...}
(10~1)~={101,1001,100001,101101,...}

그리고 (x | y) 는 x 또는 y 중에서 아무거나 하나만을 선택해서 만든 소리의 집합, 즉 집합 {x,y} 를 의미한다. 예를 들면 (1001 | 0101) 은 집합 {1001,0101}을 의미한다. 따라서 (0 | 1)~ 은 0 과 1 로 이루어진 모든 스트링의 집합, 즉 모든 소리의 집합을 말한다. 또 한 예를 보면 (100 | 11)~ 은 100 과 11 을 마음대로 섞어서 만들 수 있는 모든 소리의 집합을 의미한다. 즉 (100 | 11)~ 에 해당하는 스트링을 집합으로 나타내면 {100,11,10011,11100,100100100,1110011,...} 이 된다.

우리가 식별하고자 하는 잠수함의 엔진소리의 패턴은 다음과 같다.

(100~1~ | 01)~

여기에 속하는 소리의 예를 들어보면

1001,01,100001,010101,10000011110101,1001110101,...

이다. 다시 말해서 이것은 100~1~ 과 01 을 임의로 섞어서 만들 수 있는 모든 스트링의 집합을 나타낸다.
입력으로 0 과 1 로 구성된 스트링이 주어 질때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라.

Input

첫 번째 줄에 0, 1로 구성된 문자열이 입력된다. (최대 길이는 400)

Output

입력파일의 내용이 잠수함 소리에 부합되면 SUB를 아니면 Not SUB를 출력한다.

IO Example

입출력예시1>
입력

100000000000101

출력
SUB

입출력예시2>
입력
01001011000001

출력
Not SUB

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]