C++) 백준 10799번 풀이_쇠막대기

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

10799번: 쇠막대기

간만에 재밌는 문제를 발견했다 ㅎ 근데 좀 쉽다

 

간단히 설명하면

•  쇠막대기가 추가되는 대로 쇠막대기를 올리고, 쇠막대기가 빠지는 대로 내린다.
• 레이저가 나오면, 현재 놓인 쇠막대기를 모두 자른다. 

면 끝끝끝

 

결국 현재 시점의 막대 갯수랑, 결과값만 계산해주면 됨.

문제에 나와있는 예제를 예로 들자면...

 

 

첫 번째 레이저가 나타났을 때, 선반에 올라와있는 막대가 없으므로 자를 것이 없다.

 stick count = 0 

 res += stick count  //-> 0 

 

5번까지 처리하면 선반에는 세개의 막대기가 올라와있게 된다.

stick count = 3

res = 3 //막대기가 하나 추가될 때 마다 1씩 올려서 3이 되어있음.

7까지 처리했을 때 레이저 등장.

현재 선반에 놓인 3개의 막대기를 한번에 잘라서 6개로 만든다.

stick count = 3 

res += stick count //-> 6

 

이런식으로 계산하면 간단

막대가 하나 없어지면 stick count를 하나 줄여주기만 하면 된다

 

 

그래서 이걸 어떻게 처리할 지를 생각해보니까,

많은 버퍼는 필요없고 오직 현재 괄호랑 이전 괄호만 체크하면 될 것 같았다.

 

이전 괄호가 '('였을 때,

1. 현재 괄호가 ')'라면 -> 레이저
2. 현재 괄호가 '('라면 -> 이전 괄호가 stick 시작

이전 괄호가 ')'였을 때,

1. 현재 괄호가 ')'라면 -> stick 끝
2. 현재 괄호가 '('라면 -> 알 수 없으므로 skip

 

음..? 이렇게 나타내니까 어렵다

 

현재 괄호가 '('일 경우, 현재 괄호가 무엇을 나타내는 지 전혀 알 수 없다

그래서 현재 괄호가 '('로 들어오면 이전 괄호에 대한 처리를 해줘야 하고, ')'로 들어오면 바로 계산이 가능하다.

이전 괄호를 기준으로 하지 않고 현재 괄호를 기준으로 정리하면 아래와 같이 정리된다

 

현재 괄호가 '('일 때 

1. 이전 괄호가 '('였다면 -> 이전 괄호에 대한 stick count ++
2. 이전 괄호가 ')'였다면 -> skip

현재 괄호가 ')'일 때

1. 이전 괄호가 '('였다면 -> 레이저, res += stick count
2. 이전 괄호가 ')'였다면 -> stick 끝, stick count --

를 코드로 짜면 됩니다.

 

#include <stdio.h>

using namespace std;

int main()
{
	char bef, cur;
	int stickcnt = 0;
	int res = 0;

	bef = '0';
	while (EOF != (cur = getchar()))
	{
		if ('(' == cur)
		{
			if ('(' == bef)
			{
				stickcnt++;
				res++;
			}
		}
		else if(')' == cur)
		{
			if ('(' == bef)//razer
				res += stickcnt;
			else if (')' == bef)
				stickcnt--;
		}
		bef = cur;
	}
	printf("%d", res);
}