Asia - Jakarta - 2008/2009 - Problem B: Bonus Treasure

문제는: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4139

앞으로 ACM-ICPC 지역 예선에서 1~2문제는 쉽게 풀 수 있는데, 3~5문제를 풀 수 있으려면 어떤 공부를 해야 할까? 라는 것에 집중하고자 합니다.
그런 의미에서 각 대회에서 가장 어려웠던 문제들과 가장 쉬웠던 문제들을 제외한 나머지 문제를 다루겠습니다.

문제 B는 전체 49팀중 16팀이 푼 문제입니다. 문제 A는 17팀이 풀었으니 실제 난이도는 비슷하다고 할 수도 있겠습니다.
(그래도 A가 B보다 좀 더 어려운 것 같은 기분이 듭니다)

이 문제는 N번째 master sequence S(N)의 K번째 문자부터 이어지는 M개의 문자들을 출력하는 문제입니다.
S(N)은 괄호를 열고 S(0)부터 S(N-1)을 나열한 다음, 괄호를 닫은 문자열로 정의됩니다.

S(N)을 생성한 다음에 K번째 문자부터 M개를 읽어서 출력하면 되지 않겠는가? 라고 생각할 수 있지만, S(N)의 길이는
S(1) 의 길이가 2
S(2) 의 길이가 2+2 = 4
S(3) 의 길이가 2+4+2 = 8
S(4) 의 길이가 2+4+8+2 = 16
S(5) 의 길이가 2+4+8+16+2 = 32
S(6) 의 길이가 2+4+8+16+32+2 = 64

식으로 S(N-1)의 길이 * 2 + 2 이고, N은 최대 31이기 때문에,
S(N)의 길이는 2^N 을 넘게 됩니다. 2^31 byte이면 약 2^21 KB, 2^11 MB, 2GB 정도이므로 다음과 같이 실제로 S(N)을 생성하는 코드를 실행시키면 도저히 시간제한 안에는 돌아가지 않을 것 같아 보입니다.

#include <iostream>
#include <string>
using namespace std;

string generateS(int N) {
    if (N == 1) return string("()");
    string S("(");
   
    for(int i=0; i<N; i++) {
        S += generateS(i);
    }
    S += ")";
    return S;
}

int main() {
    generateS(32);
    return 0;
}

다행히도 S(N)은 비슷한 형태가 반복되는 형태임을 이용해서 접근해 봅시다.
예를 들어, S(4) 은 ( ( ) ( ( ) ) ( ( ) ( ( ) ) ) ) 인데요, 이것은 "(" + S(1) + S(2) + S(3) ")" 이면서,
S(3)-")" + S(3)-")" + ")" 이기도 합니다. ( ( ) ( ( ) ) ( ( ) ( ( ) ) ) )
이를 이용해서 원하는 string의 시작위치, 끝나는 위치, M+K가 S(N)의 마지막 닫는 괄호를 포함하는가? 를 case by case 처리하는 답 프로그램을 만들어 볼 수 있습니다.

S(N) 의 구조를 S(N-1)-")" + S(N-1)-")" + ")" 으로 파악한다면

1. M이 2^(N-1)-1보다 작고, M+K또한 2^(N-1)-1보다 작다면, S(N, M, K) - S(N)에서 M번째 문자부터 K개의 문자 - 는 S(N-1, M, K)와 같습니다.
2. M이 2^(N-1)-1보다 작지만, M+K가 2^(N-1)-1보다 크다면, S(N, M, K)는 S(N-1, M, 2^(N-1)-1-M) 과 S(N-1, 0, M+K-2^(N-1)+1 )와 같습니다.
3. M이 2^(N-1)-1 보다 크면, S(N, M, K)는 S(N-1, M-2^(N-1)+1, K) 와 같습니다.

M+K가 2^N과 같은 경우를 약간 다르게 처리해 주면 됩니다.

사실 정석대로(?) 라면 "(" + S(1) + S(2) + S(3) + ... ")" 구조에 따라 M번째 문자까지 나오는 (, S(1), S(2)... 등을 생략하고 K개를 추가해야 겠지만, 코딩하다가 말려서... 설명한 대로 짜봤습니다..;
소스보기