10799)쇠막대기

https://www.acmicpc.net/problem/10799

정답률 60% 넘는 게 쉬워 보여서 얘를 골랐다. 근데 완전 어려웠다.

어떻게 접근해야 할 지 몰라서 계속 헤멨던 것같다. 

몇 가지 접근을 시도했는데 성공한 접근 방법의 핵심은 레이저 하나는 막대기를 같은 갯수로 분할한다는 점이다.

그림에서 보는 것처럼 레이저는 하나의 막대기를 2 개로 분할한다.

두 개의 막대기 위에 레이저가 있으면 레이저는 총 4개로 분할한다.

나는 레이저가 막대기를 분할할 때 레이저 앞 구간과 레이저 뒷 구간으로 바라봤다.

막대기 갯수를 세다가 레이저를 만났을 때 그 갯수를 저장한다. 그 갯수가 곧 레이저에 앞 구간의 막대기 갯수이다.

문제는 레이저가 두 개 이상이 되는 경우이다.

레이저에 의해 분할 되는 구간을 다음 그림과 같이 표시했을 때 두 개의 레이저에 의해 분할되는 구간이 중첩된다.

여러 가지 방법을 생각해봤는데 가장 쉬운 방법은 레이저가 두 구간으로 분할했을 때 앞쪽 구간의 막대기 갯수만 킵하는 것이다.

다음 레이저가 막대기를 분할하면 그때도 그 레이저에 의해 분할된 앞쪽 구간의 막대기 갯수를 킵하면 된다.

이렇게 되면 마지막 레이저에 의해 분할된 뒷쪽 구간의 막대기 갯수를 킵하지 못하는데, 반복문을 빠져나오고 그 갯수를 킵하면 된다.

문제는 여기서 끝나지 않는다.

위 그림에서 박스 표시해둔 구간을 보면 세 번째 레이저를 만나기도 전에 막대기가 끝이난다.

나는 막대기가 시작할 때 count 갯수를 올리고 막대기가 끝날 때 count 갯수를 감소시켰다.

세 번째 레이저를 만나기도 전에 막대기가 끝나버리면 총 막대기 갯수를 세는 데 필요한 정보가 손실된다.

따라서 막대기가 끝날 때 count 갯수는 줄이되 레이저를 만나지 못해 손실되는 것을 막기 위해 tempCount를 증가시킨다.

그리고 레이저를 만났을 때 지금까지 셌던 막대기의 갯수 count와 손실된 막대기 갯수 tempCount를 더하면,

레이저에 의해 분할된 구간에서 온전한 막대기 갯수를 얻을 수 있다. 그리고 tempCount를 0으로 초기화한다.

 

#include<stdio.h>
 
int main() {
    char tempStr[100001];
    int barCount = 0; 
    int count = 0;
    int tempCount = 0;
 
    gets(tempStr);
 
    for (int i = 0; tempStr[i] != NULL;i++) {
        if (tempStr[i]=='('&&tempStr[i+1]==')') {
            barCount += count + tempCount;
            tempCount = 0;
            i++;
        }
        else if (tempStr[i]=='(') {
            count++;
        }
        else if (tempStr[i]==')') {
            count--;
            tempCount++;
        }
    }
    barCount += count + tempCount;
 
    printf("%d\n",barCount);
 
    return 0;
}