ACM준비/algospot

BRACKETS

조규현15 2015. 7. 30. 13:41
반응형

https://www.algospot.com/judge/problem/read/BRACKETS

 

algospot.com :: BRACKETS

Brackets 문제 정보 문제 We give the following inductive definition of a “regular brackets” sequence: the empty sequence is a regular brackets sequence, if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and if a

www.algospot.com

DP문제.

여러 방법이 있다.

1. 오토마타처럼 regular bracket은 ' ( ) ' , ' [ ] ' , ' ' 이고 이것들의 조합이 regular brackets이다.

이것들의 연속된 string을 만들면 string 개수가 정답이다.

2. DP로 접근한다. array의 1'st index부터 end까지 index의 Character를 보고 차후에 발견될 Character를 검색한다.

검색하는 과정에서 발견된다면 이는 2가지로 분기가 된다.

- 왼쪽 내부와 오른쪽 내부의 DP 값의 합 + 2이 또는 그냥 지나치고 index + 1부터 end Index의 합이다.

- 이 때, 2차원 배열을 사용하면 DP로 풀게된다.

 

#include <string.h>

#include <stdio.h>

#define max(a, b) (a >= b) ? a : b

char INPUT[101];

int MAP[101][101];

int findIndex(int src, int des, char CHAR)

{

    for (int i = src; i <= des; i++)

        if (INPUT[i] == CHAR)

            return i;

    return -1;
}

int BRACKETS(int src, int des)

{

    if (src >= des)
        return 0;

    else if (MAP[src][des] != -1)
        return MAP[src][des];

    int &MAXCOUNT = MAP[src][des] = 0;

    if (INPUT[src] == '(' || INPUT[src] == '[')

    {

        char DESTINATION = (INPUT[src] == '(') ? ')' : ']';

        int START = src + 1;

        int LAST;

        while ((LAST = findIndex(START, des, DESTINATION)) != -1)

        {

            MAXCOUNT = max(MAXCOUNT, (2 + BRACKETS(src + 1, LAST - 1) + BRACKETS(LAST + 1, des)));

            START = LAST + 1;
        }
    }

    return MAXCOUNT = max(MAXCOUNT, BRACKETS(src + 1, des));
}

int main()

{

    for (scanf("%s", &INPUT); (strcmp(INPUT, "end") == 0) ? 0 : 1; scanf("%s", &INPUT))

    {

        memset(MAP, 0xFF, sizeof(MAP));

        printf("%d\n", BRACKETS(0, strlen(INPUT) - 1));
    }

    return 0;
}
반응형

'ACM준비 > algospot' 카테고리의 다른 글

GRIDISLANDS - 2  (0) 2015.07.30
GRIDISLANDS  (0) 2015.07.30
WORDLENGTH  (0) 2015.07.09
SENTENCE  (0) 2015.07.07
PASS486  (0) 2015.07.07