[Hard] Stackol

program 에 C가 등장하면 그 순간 스택의 내용물을 모두 출력하고 스택을 비운다 따라서 program 을 C로 나누면 각각 나뉜 부분은 다른 부분에 영향을 끼치지 못한다 이를 통해 dp를 생각할 수 있다 D[i][j] = C를 i개 사용해서 출력을 output[j] 까지 만드는 프로그램의 개수 (C로 끝나야 함) = sum( D[i-1][p] * count(p+1, j) ) count(i, j) = output[i] ~ output[j] 를 생성하는 A,B 만으로 이루어진 프로그램의 개수 D를 구하는데 O(k*n*n) 이 걸리므로 count(i, j) 를 계산하는데 O(1) 이 되도록 해야한다. 이게 어려운 부분... 시뮬레이션을 하면서 느린 알고리즘을 먼저 만들어보자. 예를 들어 BBABABAA 라는 output이 있다. program이 끝나면 스택1의 내용물을 모두 출력하고 그 이후에 스택2의 내용물을 출력한다. 따라서 output의 어느 점을 기준으로 왼쪽은 스택1에 있던 글자고, 오른쪽은 스택2에 있던 글자다. 그 위치를 5번째라고 해보자. BBABA | BAA 인 상황이다. program의 맨 첫번째 글자는 무엇일까? 바로 왼쪽 부분의 마지막 글자다. 우선 program의 맨 첫번째 글자이므로 스택1에 들어간 글자이고, 스택에 들어갔다 나오면 순서가 뒤집히기 떄문이다. program의 두번째 글자는? 첫번째 글자가 A였으므로 왼쪽 부분의 마지막에서 두번째글자다. program의 세번째 글자는? 두번째 글자가 B였으므로 이번엔 오른쪽 부분의 마지막 글자다. 이런식으로 포인터 2개를 놓고 시뮬레이션을 하면서 program 을 복원해낼 수 있다. 스택1과 스택2를 나누는 경계를 모든 위치에 두어보고, program을 성공적으로 복원해낼 수 있으면 경우의수를 하나씩 세면 된다. O(n*n) 이다. 잘 생각해보면 스택1의 크기를 한번에 알 수 있다. nA = program에 있던 A의 개수 = output에 있는 A의 개수 라 하자. program에서 A 바로 다음에 나오는 글자는 모두 스택1로 들어간다. 따라서 스택1의 크기는 무조건 nA (마지막 글자가 A인 경우) 혹은 nA+1 (마지막 글자가 B인 경우) 이다. O(n) 이다. 위에서 시뮬레이션 하는 과정을 잘 살펴보자. 왼쪽 부분에서 글자 A가 중요할까? 왼쪽 부분에서 글자 A를 만나면 그걸 program에 추가하고 다시 왼쪽 부분을 찾는다. 따라서 왼쪽 부분에서 글자 A는 필요없다. 마찬가지로 오른쪽 부분에서 글자 B는 필요없다. 우리는 output 문자열을 적당히 변환하여 다음과 같은 4가지 정보만을 남길 것이다. lB : 왼쪽 부분에 있는 B의 개수 rA : 오른쪽 부분에 있는 A의 개수 lbB : 왼쪽 부분이 B로 시작하는가 rbA : 오른쪽 부분이 A로 시작하는가 (혹은 오른쪽 부분이 비어있는가) 1) if lB == rA 왼쪽의 B의 개수와 오른쪽의 A의 개수가 같으므로 왔다갔다 하다가 lB = 0 && rA = 0 인 상황까지 갈 것이다. 이때는 오른쪽에서 마지막 A를 막 처리하고 난 상황이다. 오른쪽에서 마지막 A를 처리하고 왼쪽으로 넘어오면 왼쪽에 남은 A들을 쭉 처리하고 끝나야 정상이다. 만약 이 때 비정상이려면, 이후에 오른쪽에 글자가 남아있어야 하는데, 남아있을 수 있는 글자는 B 뿐이다. 따라서 rbA == true 여야 올바른 program 이 된다. 2) if lB == rA + 1 위와 비슷하게 왔다갔다 하다가 lB = 0 && rA = 0 인 상황까지 오면 이때는 왼쪽에서 마지막 B를 막 처리하고 난 상황이다. 왼쪽에서 마지막 B를 처리하고 오른쪽으로 넘어오면 오른쪽에 남은 B들을 쭉 처리하고 끝나야 정상이다. 만약 이 때 비정상이려면, 이후에 왼쪽에 글자가 남아있어야 하는데, 남아있을 수 있는 글자는 A 뿐이다. 따라서 lbB == true 여야 올바른 program 이 된다. 3) if lB > rA + 1 lB가 rA에 비해 많이 커지면 왔다갔다 한 후 오른쪽으로 넘어와서 오른쪽을 다 처리해도 항상 왼쪽에 글자가 남는다. 따라서 올바르지 않은 program 이다. 4) if lB < rA lB가 rA보다 작으면 왔다갔다 한 후 왼쪽으로 넘어와서 왼쪽을 다 처리해도 항상 오른쪽에 글자가 남는다. 따라서 올바르지 않은 program 이다. 위의 4가지 조건을 통해 ( (lB == rA) && rbA ) || ( (lB == rA + 1) && lbB ) 이면 올바른 program 이라는 것을 알 수 있다. 그리고 이건 prefix sum 을 구해놓으면 O(1)에 확인할 수 있다.