1013 - Contact
본문
“무한히 넓은 저 우주에 인류만이 홀로 존재한다면, 그건 정말 슬픈 일이 아닐까요”
푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으로부터의 전파를 수신하기 위해 밤하늘을 바라보고 있다.
이 망원경이 수집한 전파 속에서 자연적으로 발생하기 힘든 패턴들을 찾아내어, 그것을 증거로 외계 문명의 존재 여부를 가리려는 노력은 줄곧 이어져왔지만 아직까지도 그러한 패턴은 발견되지 않았다. 한국 천문학계의 자존심 김동혁 박사는 국내 기술로 이러한 탐사를 진행하기 위하여 다음의 전파 표기를 표준으로 삼았다.
전파의 기본 단위는 { 0 , 1 } 두 가지로 구성되어있으며, x+ ( ) 는 임의의 개수(최소 1개) x의 반복으로 이루어진 전파의 집합을 나타낸다.
(xyx)+ ( ) 는 괄호 내의 xyx의 반복으로 이루어진 전파의 집합을 뜻한다. 아래는 이해를 돕기 위한 예제이다.
1+ = { 1, 11, 111, 1111, 11111, … }
10+ = { 10, 100, 1000, 10000, 100000, … }
(01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }
(1001)+ = { 1001, 10011001, 100110011001, … }
10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }
(10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }
반복을 의미하는 + 외에도 or 를 의미하는 | 기호가 있다. { x | y } 는 x 혹은 y 를 의미하는 것으로, { 0+ | 1+ } 는 { 0 , 1 , 00 , 11 , 000 , 111 , … } 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.
- (100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }
최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.
- (100+1+ | 01)+
김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 $1 \leq N \leq 200$의 범위를 갖는다.
출력
각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다. 출력 문자열은 모두 대문자로 구성되어 있다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 512MB |
- $1 \leq N \leq 200$
풀이
떠오르는 공식이 없다면 일단 case work를 진행하자.
- 첫 숫자가 0인 경우 [case 1]
- 01인 경우만 첫 숫자가 0일 수 있으므로, 뒤가 1이 아니라면 NO [case 2]
- 뒤가 1이라면 처음으로 되돌아감 [case 3]
- 첫 숫자가 1인 경우 [case 4]
- 첫 숫자가 1이라면 뒤에 0이 최소 2개 이상 나와야 함. 아니라면 NO [case 5]
- 그 다음에는 1이 최소 1개 이상 나와야 함. 아니라면 NO [case 6]
- 만약 1이 1개밖에 나오지 않고 바로 0이 나왔다면, 이 상황은 첫 숫자가 0인 경우의 상황임 [case 7]
- 다음 0이 나올 때까지 기다린 후, 아래 분기점에 따라 상황을 판단
- 만약 0이 나오지 않았다면, 문자열 종료. YES [case 8]
- 나온 0이 1개만 존재하는 경우, 이 0부터 첫 숫자가 0인 경우로 생각할 수 있음 [case 9]
- 나온 0이 2개 이상인 경우, 이전 1부터 첫 숫자가 1인 경우로 생각할 수 있음 [case 10]
- NO를 출력하지 않고 문자열이 종료된 경우 YES [case 0]
위 조건을 하나로 묶을 수 있는 함수 구조가 떠오르지는 않는다.. 위 조건을 분기점으로 계속 가져올 수 있는 조건문을 추가하여 결과를 반환하자.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 10
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
67
68
69
70
71
72
73
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (200 + 1)
char result[2][4] = {"NO", "YES"};
bool retval;
int main() {
int t;
scanf("%d", &t);
while (t--) {
char str[MAX_IDX];
scanf("%s", str);
int cur = 0;
while (true) {
if (str[cur] == '\0') { // case 0
retval = true;
break;
} else if (str[cur] == '0') { // case 1
if (str[cur + 1] != '1') { // case 2
retval = false;
break;
} else { // case 3
cur += 2;
continue;
}
} else if (str[cur] == '1') { // case 4
int zeroCount = 0;
++cur;
while (str[cur] == '0') {
++cur;
++zeroCount;
}
if (zeroCount < 2) { // case 5
retval = false;
break;
}
int oneCount = 0;
while (str[cur] == '1') {
++cur;
++oneCount;
}
if (oneCount < 1) { // case 6
retval = false;
break;
} else if (oneCount == 1) { // case 7
continue;
}
if (str[cur] == '\0') { // case 8
continue;
} else if (str[cur + 1] == '0') { // case 10
--cur;
continue;
} else { // case 9
continue;
}
}
}
printf("%s\n", result[retval]);
}
return 0;
}
- 코드의 조건문 부분에 번호를 기입하여 어떤 조건을 수행하는지를 주석으로 달아두었음
retval: 문자열의 결과를 기록