[python] 백준 10799 쇠막대기

문제 링크

 

www.acmicpc.net/problem/10799

10799번: 쇠막대기

문제 요약

 

'('와 ')'로 이루어진 문자열로 레이저와 쇠막대기의 배치 정보를 준다면 쇠막대기 조각의 총 개수를 구하라.

 

문제 풀이

 

문제 속의 그림에 다른 정보들을 추가해보겠습니다.

문제 설명용 이미지인데 너무 작네요

쇠막대기에 적혀진 숫자들은 잘려진 조각을 세기 위한 숫자입니다. 그 위쪽 괄호와 근접하게 적힌 숫자들은 무엇일까요?? 괄호가 열린 만큼 쇠막대기들이 겹쳐서 쌓여있게 됩니다. 즉 몇겹이 쌓아 올려져 있는지 적어놨습니다. 레이저를 만나게 된다면 그 개수만큼 더해주세요. 괄호가 닫히게 되면 쌓여있는 쇠막대기의 숫자는 줄어들지만, 조각의 수는 하나 늘어남을 인지해주세요.

 

소스 코드

import sys
input = sys.stdin.readline

s = input().rstrip()

ans = 0 #조각
cnt = 0 #겹쳐진 쇠막대기

for i in range(len(s)):
    if s[i] == ')':
        if s[i-1] == '(':
            if cnt != 0:
                cnt -=1
            else:
                cnt = 0
            ans+=cnt
        else:
            ans += 1
            cnt-=1
    else:
        cnt += 1
print(ans)