[백준/10799/파이썬] 쇠막대기

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

10799번: 쇠막대기

조건

• () : 레이저를 의미한다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

입력

IN ()(((()())(())()))(()) OUT : 17

IN (((()(()()))(())()))(()()) OUT:24

SOL)

이 문제는 VPS , Prev Mission의 괄호찾기의 응용인거 같음. 따라서, 스택을 이용하면 됨!

1. 레이저를 찾아야함. → stack을 이용해서, '(' 는 쌓아주고 , ')'를 만나면, pop 해주면 됨.
2. 막대기가 끝나는 경우를 알아야함. 레이저도 ')'경우로 끝나고, 쇠막대기도 ')'로 끝남. ⇒ 생각 해보니, ')' 다음 ')'이 오면, 막대기가 끝남.
3. 그럼, 레이저 갯수는 쉽게 알 수 있는데, 짤리는 갯수를 어떻게 정해줄까?

'(' 인경우, stack에 쌓아주기만 하면됨.

')' 인 경우 →2가지로 생각 가능하다는 결론에 도달.

• 1. ) )이 오면 , 막대기가 끝남.
• 2. ()이면 레이저임.

스택에 쌓아놓고 , ')'인 경우 pop만 해주면, 다 레이저로 생각될 수 있으니까, 그러면 안됨!

따라서, 입력되는 친구는 알고 있기 때문에, 입력 되는 친구를 이용하면 풀 수 있을거 같음.

그럼 이제, 잘리는 철의 갯수를 어떻게 생각해주냐가 문제임.

이건 그림으로 생각해보자.

코피아닙니다.

 

• '('의 갯수는 막대기의 갯수를 의미합니다. 그럼, 일단 레이저를 만났으면, 잘림!. 레이저를 만났을 때, 쌓여있는 '('의 갯수만큼은 일단 철조각이 생깁니다.
• ')' 다음 ')' 이오면, 막대기가 끝난거니까, 마지막 끝 조각도 더해줘야함!

import sys
input = sys.stdin.readline()
stk=[]
ans=0
pipes = input()

for idx in len(pipes):
	if p == '(' :
		stk. append(pipes[idx])
	else: # ')'인 경우,
		if pipes[idx-1] == '(': #레이저인 경우
			stk.pop()
			ans+=len(stk)
		else:
			stk.pop()
			ans+=1
print(ans)
#이런느낌 !