BOJ 10799 - 쇠막대기

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

문제

스택 문제로 유명한 한국정보올림피아드(KOI) 2015 지역본선 문제, 쇠막대기입니다. 사실 스택 없이 풀리는 문제지만요.

문제를 읽어보면 쇠막대기의 왼쪽 끝은 여는 괄호, 오른쪽 끝은 닫힌 괄호로 표시하여, 레이저 "()"에 의해 잘려진 막대기 조각이 총 몇 개인지 구하는 문제입니다.

잘못된 모양은 없다고 하니 스택으로 별다른 검증은 안해도 됩니다.

풀이

먼저 풀이의 중간 단계를 생각해봅시다. 문자열 "((()()))"은 쇠막대기가 2층으로 쌓인 형태일 것이고, 위 사진처럼 레이저(노란색 점선)에 의해 잘려나갈겁니다.

여기서 첫 번째 레이저에 집중해봅시다.

첫 번째 레이저가 발사된다면 1층에서 2조각, 2층에서 2조각으로 나뉘어서 총 4조각이 되겠죠. 근데 이런식으로 전체의 결과를 각 레이저마다 구해야한다면 항상 전체를 봐야합니다.

이 문제는 레이저를 앞쪽부터 차례대로 살피면서, 현재 레이저를 기준으로 왼쪽으로 몇 개의 조각이 생겼는 지만 세어보면 됩니다.
즉, 항상 왼쪽만 보면 됩니다. 왜냐하면 첫 번째 레이저의 오른쪽은 두 번째 레이저의 왼쪽에 의해 구해질 것이기 때문입니다.

다시 돌아와서 첫 번째 레이저는 왼쪽으로 2조각을 만듭니다. 이것은 쇠막대기가 쌓인 층의 개수, 즉 이전까지 등장한 쇠막대기의 시작을 의미하는 열린 괄호의 개수와 같습니다. 

두 번째 레이저 역시 왼쪽으로 2조각을 만들어냅니다. 첫 번째 레이저가 쇠막대기 하나를 사라지게 한 것은 아니므로 그대로 2층만큼 쌓여있기 때문에 첫 번째 레이저와 똑같습니다.

그럼 층이 달라지는 경우는 어떻게 할까요?

괄호가 닫힐 때, 레이저의 일부가 아닌 경우에는 층이 바뀌는 것을 의미합니다.

해당 층에서 나타난 가장 마지막 레이저의 왼쪽으로 생기는 조각은 이미 모두 세었으므로, 세지 못한 1개의 조각만 더해줍니다.

이런 이유로, 닫힌 괄호가 등장할때마다 이전까지 쌓인 열린 괄호의 개수의 합이 정답이 되는 것입니다.

코드