잠수함 식별 - KOI 1996

BOJ - 잠수함 식별

잠수함은 물 속에서 소리를 낼 때 일정한 규칙성을 갖는 소리를 낸다. 0과 1로 구성되는 소리의 집합이 있을 때, 현 집합이 잠수함이 내는 소리인지 잡음인지를 판별해야 한다.

주어진 소리 집합이 잠수함이 내는 소리이려면 다음 패턴을 만족해야 한다.

(100~1~|01) ~

여기서 ~은 그 앞에 묶여있는 부분집합이 반복됨을 의미하며, a | b 는 a 또는 b 둘 중 하나가 해당되는 것을 의미한다.

즉, 100~1~ 은 1 이후 0이 반복되고, 그 이후 1이 반복되는 패턴을 의미하며, (100~1~|01) ~ 는 (100~1~ 또는 01) 패턴이 반복됨을 의미한다.

이전에 문제를 풀었을 때에 먼저 떠오른 방법과, 며칠 전 문제를 풀었을 때에 먼저 떠오른 방법이 달랐었고, 둘 다 괜찮은 아이디어를 기반으로 하기에(효율은 다르지만) 해법을 작성해본다.

O(N^3) - DP

최근에 풀었을 때 가장 먼저 떠오른 풀이, N 제한이 작기 때문에 풀린다(당시 대회 상황에서 가능했는지 여부는 모르겠다).

DP를 생각할 때에 기반이 되는 요소는 주어지는 소리가 잠수함이 내는 소리일 경우, 특정한 패턴이 반복된다는 것이다. 즉, 현재 주어진 소리를 A와 B, 두 개의 부분집합으로 나눠서 둘 다 잠수함이 내는 소리를 만족한다면, A와 B를 합친 집합도 잠수함이 내는 소리임을 만족한다.

따라서 다음 DP를 고안할 수 있고, 성립함을 알 수 있다.

DP[i][j] = 주어진 소리의 부분집합, 폐구간 [i, j]로 구성된 소리가 잠수함이 내는 소리인지에 대한 여부 -  True or False

DP[i][j] = ( DP[i][k] && DP[k + 1][j] )     -    ( 단, i < k < j - 1)

기저 - DP[i][j] = (100~1~) or (01) 일 경우는 True

O(N) - Automata

이전에 풀었던 방법은 오토마타와 접근은 같았지만, 그 구현을 오로지 조건문으로만 해결했었다.

오토마타란, 각각의 상태에 대해서 일정한 입력이 들어오면, 입력에 따라서 다른 상태로 현 상태를 이동(상태를 전이)하는 방식을 수행하면서 동작 및 결과를 내는 방식이다. 즉, 각각 상태 스테이트가 존재할 때, 현재 스테이트에서 들어오는 입력에 따라 다른 상태 스테이트로 현 상태를 전이하며 진행된다.

더 자세한 내용을 배울 수 있는 사이트를 참조하겠다.

오토마타 이론 - 위키피디아(ko)     오토마타 이론 - 위키피디아(en)    

이를 잠수함 판별 문제에 적용시키기 위해서는 잠수함 판별 문제가 각 상황을 스테이트로 나타낼 수 있으며, 이러한 스테이트를 유한하게 정의할 수 있음을 알아야 한다.

잠수함 판별 문제의 유한 상태 스테이트를 만들면 다음과 같이 만들 수 있다.

즉, 각각의 상태에서 주어지는 입력에 따라 다른 인덱스를 가지는 상태로 현 상태를 전이한다. 그 과정에서 F(실패) 상태로 가게 되면 어떠한 경우에도 자기 자신으로 이동하게 되는 것이다(현 상황에서는 잡음으로 판별되는 경우가 F 상태이다).

각각의 상태에서 최종 결과가 잠수함의 소리이려면 4, 5, 8번의 상태여야 함을 알 수 있다(각각의 상태가 잠수함의 기저 상황이며, 그 상태 이전에 있던 상태들은 오토마타를 진행하면서 잠수함이 내는 소리라고 이미 판별되었으므로).

이를 이용해 S(초기) 상태에서 입력에 따라 상태를 전이시키면서 진행한 이후, 최종 상태가 4, 5, 8번일 경우 잠수함의 소리, 그렇지 않을 경우 잡음이라는 결과를 출력하는 것으로 해결할 수 있다.