BOJ 10799 쇠막대기

문제

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    lines = input().strip()
    stick = 0
    cnt = 0

    for i in range(len(lines)):
        if lines[i] == "(":
            stick += 1
        else: # ) 
            stick -= 1

            if lines[i - 1] == "(": # 레이저
                cnt += stick
            else: # 막대기
                cnt += 1

    print(cnt)

 

stick은 현재 열려 있는 쇠막대기 개수, cnt는 최종 조각 개수이다.

 

( 를 만났을 때에는 새로운 막대기가 시작되므로 (혹은 레이저의 시작 후보), 현재 열려있는 막대기 수에다가 1을 더한다.

if lines[i] == "(":
    stick += 1

 

) 를 만나게 되었을 때에는 막대기 끝이나 레이저나 무조건 하나를 닫는 역할이기에 현재 열려 있는 쇠막대기 개수 중 하나를 제거한다.

else:
	stick -= 1

 

이제 레이저인지 판단한다. ) 일때 바로 앞 문자열이 ( 이면 레이저이기 때문이다.

따라서 레이저라면 현재 열려 있는 모든 막대기를 자르므로 레이저를 제외한 진짜 막대기 개수를 더한다.

if lines[i-1] == "(":
	cnt += stick

 

레이저가 아닌 막대기 끝이라면 막대기 하나가 끝나므로, 마지막 조각 1개를 추가한다.

else:
	cnt += 1

 

예제

만약 입력이 아래와 같을때,

()(((()())(())()))(())

 

아래와 같이 수행된다.

(
→ stick = 1

()
→ stick = 0
→ 레이저 → cnt += 0

(
→ stick = 1

(
→ stick = 2

 

 

정리

반복하면서:

( → 막대기 시작 → stick += 1
) → 하나 닫음 → stick -= 1
바로 앞이 ( → 레이저 → cnt += stick
바로 앞이 ) → 막대기 끝 → cnt += 1

 

 

솔직히 나는 풀기 어려웠다. 일단 문제 자체를 이해하기 어려워서 챗 선생과 과외를 진행했다.

독해력이란 게 전부인 것 같다..