티스토리 뷰

ICPC/2013 인터넷예선

G. Moore Machine

전명우 2013.09.29 17:52


ProblemG_Eng.pdf


문제에서 주어진 식을 그래프 DAG(Directed Acyclic Graph)로 잘 만들어주면, 비교적 쉽게 풀리는 문제다.


한 마디로, 이 문제를 노가다성 문제라고 생각한다.


DAG를 구성하는 방법은 구체적으로 설명하지 않겠다. 까다로울 수 있지만 특별한 알고리즘이 필요한 것도 아니고 사람마다 저마다의 방법이 있을 것이라 생각하기 때문이다.


필자는 A(B|CD(E|_)G)E 가 입력으로 들어오면 아래와 같이 그래프를 구성했다.



그래프를 구성 한 뒤에는 DP(Dynamic Programming)을 통해 해결하면 된다.

그래프를 구성하는 노드의 개수를 $N$이라 하고, 입력으로 주어지는 두 번째 문자열의 길이를 $L$이라 하자.

우선 그래프에서 위상정렬를 통해 각 노드의 순서를 구한 뒤 그 순서대로 처리한다.


다이나믹 배열의 정의는 아래와 같다.

D[i][j] = 노드 i에서 주어진 문자열 j번째 문자까지 만들 수 있다. 없다.


점화식은 따로 설명하지 않겠다.

위 정의로는 언더바(_) 가 없을 때 두 문자열이 매치가 되는지 $O(NL)$ 시간 안에 판별 할 수 있다.


언더바에 대한 처리도 까다롭지 않다.

D[i][j] = _ or alphabet or ! 중 가능한 최고 우선순위

라고 정의를 해보자.

우선 순위는 _ 가 가장 앞서며 alphabet이 다음이고 !가 마지막이다.

이때 D[N][L] 을 출력해주기만 하면 된다.


G.cpp



'ICPC > 2013 인터넷예선' 카테고리의 다른 글

I. Pickup Game  (2) 2013.09.29
H. Networks with Unidirectional Links  (2) 2013.09.29
G. Moore Machine  (0) 2013.09.29
F. KCPC  (0) 2013.09.29
E. Falling Ants  (0) 2013.09.29
D. 이중 우선순위 큐  (0) 2013.09.29
댓글
댓글쓰기 폼