[동적 기획] 삼색 두 갈래 나무

삼색 두 갈래 나무
Time Limit:1s
Memory limit:32M
Accepted Submit:81
Total Submit:211
한 그루의 두 갈래 나무는 다음과 같은 규칙에 따라 0, 1, 2로 구성된 문자 서열을 나타낼 수 있으며, 우리는'두 갈래 나무 서열 S'라고 부른다.
예를 들어 다음 그림에 표시된 두 갈래 트리는 두 갈래 트리 시퀀스 S=2200110으로 표시할 수 있다.
너의 임무는 두 갈래 나무의 노드를 염색하는 것이다.각 노드는 빨간색, 녹색, 파란색으로 염색할 수 있다.그리고 하나의 노드와 그 하위 노드의 색깔은 반드시 달라야 한다. 만약에 이 노드가 두 개의 하위 노드가 있다면 이 두 개의 하위 노드의 색깔도 같지 않아야 한다.두 갈래 나무의 두 갈래 나무 서열을 정하고 이 나무 중 가장 많고 적어도 몇 개의 점이 녹색으로 물들 수 있는지 요청합니다.
출력 형식 가져오기
입력 데이터는 여러 그룹의 데이터로 구성되어 있다.각 그룹의 데이터는 한 줄만 있고 10000자를 넘지 않으며 두 갈래 트리 서열을 나타낸다.각 그룹의 입력 데이터에 대해 출력은 한 줄에 두 개의 정수만 포함하고 가장 많은 점과 적어도 몇 개의 점이 녹색으로 물들 수 있는지 순서대로 표시한다.
샘플 입력

1122002010

샘플 출력

5 2

#include 
#include 
#include 
#include 

#define top_num 2
#define min_top 0
#define max_top 1

#define is_green 0
#define no_green 1

#define MAX_NUM(x, y) ((x) > (y) ? (x) : (y))
#define MIN_NUM(x, y) ((x) < (y) ? (x) : (y))

int main()
{
    int i, len, top[top_num];
    int isa, noa, isb, nob;
    int min_num, max_num;
    int stack[top_num][2][10010];
    char *p, str[10010];

    while(scanf("%s", str) != EOF)
    {
        len = strlen(str);
        p = &str[len - 1];
        top[min_top] = top[max_top] = 0;
        for (i = 0; i < len; ++i, --p)
        {
            switch(*p)
            {
            case '0':
                stack[min_top][is_green][top[min_top]] = 1;
                stack[min_top][no_green][top[min_top]] = 0;
                ++top[min_top];

                stack[max_top][is_green][top[max_top]] = 1;
                stack[max_top][no_green][top[max_top]] = 0;
                ++top[max_top];
                break;
            case '1':
                --top[min_top];
                isa = stack[min_top][is_green][top[min_top]];
                noa = stack[min_top][no_green][top[min_top]];
                stack[min_top][is_green][top[min_top]] = noa + 1;
                stack[min_top][no_green][top[min_top]] = MIN_NUM(isa, noa);
                ++top[min_top];

                --top[max_top];
                isa = stack[max_top][is_green][top[max_top]];
                noa = stack[max_top][no_green][top[max_top]];
                stack[max_top][is_green][top[max_top]] = noa + 1;
                stack[max_top][no_green][top[max_top]] = MAX_NUM(isa, noa);
                ++top[max_top];
                break;
            case '2':
                --top[min_top];
                isa = stack[min_top][is_green][top[min_top]];
                noa = stack[min_top][no_green][top[min_top]];
                --top[min_top];
                isb = stack[min_top][is_green][top[min_top]];
                nob = stack[min_top][no_green][top[min_top]];
                stack[min_top][is_green][top[min_top]] = noa + nob + 1;
                stack[min_top][no_green][top[min_top]] = MIN_NUM(isa + nob, isb + noa);
                ++top[min_top];

                --top[max_top];
                isa = stack[max_top][is_green][top[max_top]];
                noa = stack[max_top][no_green][top[max_top]];
                --top[max_top];
                isb = stack[max_top][is_green][top[max_top]];
                nob = stack[max_top][no_green][top[max_top]];
                stack[max_top][is_green][top[max_top]] = noa + nob + 1;
                stack[max_top][no_green][top[max_top]] = MAX_NUM(isa + nob, isb + noa);
                ++top[max_top];
                break;
            default:
                break;
            }
        }

        --top[min_top];
        isa = stack[min_top][is_green][top[min_top]];
        noa = stack[min_top][no_green][top[min_top]];
        min_num = MIN_NUM(isa, noa);
        --top[max_top];
        isa = stack[max_top][is_green][top[max_top]];
        noa = stack[max_top][no_green][top[max_top]];
        max_num = MAX_NUM(isa, noa);

        printf("%d %d
", max_num, min_num);
    }

    return 0;
}