백준 10799번 쇠막대기 Python

✅ 백준 10799번 쇠막대기

🔷 문제

문제출력

여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.
• 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있습니다.

• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 () 으로 표현됩니다. 또한, 모든 ()는 반드시 레이저를 표현합니다.
• 쇠막대기의 왼쪽 끝은 여는 괄호 ( 로, 오른쪽 끝은 닫힌 괄호 ) 로 표현됩니다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 예를 들어 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려집니다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하십시오.

테스트케이스

예제 입력 1

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

예제 출력 1

17

문제설명

이 문제는 스택 개념을 사용하여 레이저 절단 시 조각 수를 세는 문제입니다.

쇠막대기와 레이저를 괄호로 표현했을 때, ()는 레이저, 그 외의 괄호 쌍은 쇠막대기를 의미합니다.

• 여는 괄호 ( 를 만나면 쇠막대기가 새로 시작되므로 스택에 push 합니다.
• 닫는 괄호 ) 를 만나기 전에 바로 앞이 ( 였다면 () 이므로 레이저입니다.

이 경우, 스택에 있는 쇠막대기 개수만큼 조각이 늘어납니다.

• 닫는 괄호 ) 를 만나는데 바로 앞이 ( 가 아니라면, 이는 쇠막대기의 끝입니다.

따라서 스택에서 하나 pop 하고, 끝난 쇠막대기 조각 1개를 더합니다.

사례 기반 설명

1. () → 레이저
   예시: ()
   레이저가 하나 있으면, 현재 쌓여있는 모든 쇠막대기를 한 번씩 절단합니다.
   예를 들어, 쇠막대기가 3개 쌓여있다면 ()가 나올 때 3개의 조각이 새로 생깁니다.


2. (()) → 쇠막대기 1개
   이 경우, 바깥쪽 ( 와 ) 가 쇠막대기를 감싸고 있고, 안쪽에는 레이저 ()가 있습니다.
   예를 들어, (()()) 라면 레이저가 2번 작동하여 막대기가 3개의 조각으로 나눠집니다.


3. ((())) → 긴 쇠막대기 안에 짧은 쇠막대기
   바깥 쇠막대기 시작 → 안쪽 쇠막대기 시작 → 쇠막대기 끝 순서로 스택에서 개수를 세면 됩니다.
   레이저 위치에 따라 조각 개수가 달라집니다.

🔷 아이디어

시뮬레이션 규칙

• cnt = 현재 열려 있는 막대 개수
• sum_cnt = 최종 조각 개수
• 레이저(()) → cnt-- 후, sum_cnt += cnt (남아 있는 막대 수만큼 조각 추가)
• 막대 끝(), 앞이 )인 경우) → cnt--, sum_cnt++ (마지막 조각 1개 추가)
• 시각화는 cnt 값만큼 ---를 층층이 쌓아 표시

문자열: ()(((()())(())()))

1. (
   괄호 상태: (
   시각화:

   ---

   cnt = 1, sum_cnt = 0
   이유: 새 막대 시작


2. )
   괄호 상태: \`\` (비어있음)
   시각화:

   (없음)

   cnt = 0, sum_cnt += 0 → sum_cnt = 0
   이유: 레이저이지만 쌓인 막대 없음 → 조각 증가 없음



---

3. (
   괄호 상태: (
   시각화:

   ---

   cnt = 1, sum_cnt = 0
   이유: 새 막대 시작


4. (
   괄호 상태: ((
   시각화:

   ---
   -----

   cnt = 2, sum_cnt = 0
   이유: 막대 1개 위에 새 막대 시작


5. (
   괄호 상태: (( (
   시각화:

   ---
   -----
   -------

   cnt = 3, sum_cnt = 0


6. (
   괄호 상태: ((((
   시각화:

   ---
   -----
   -------
   ---------

   cnt = 4, sum_cnt = 0



---

7. )
   괄호 상태: (((
   시각화:

   ---
   -----
   -------

   cnt = 3, sum_cnt += 3 → sum_cnt = 3
   이유: 레이저 → 현재 남은 3개의 막대가 각각 잘려서 3조각 증가


8. (
   괄호 상태: ((((
   시각화:

   ---
   -----
   -------
   ---------

   cnt = 4, sum_cnt = 3
   이유: 새 막대 시작


9. )
   괄호 상태: (((
   시각화:

   ---
   -----
   -------

   cnt = 3, sum_cnt += 3 → sum_cnt = 6
   이유: 레이저 → 3개 막대가 잘려서 3조각 추가



---

10. )
    괄호 상태: ((
    시각화:

    ---
    -----

    cnt = 2, sum_cnt++ → sum_cnt = 7
    이유: 막대 끝 → 마지막 조각 1개 추가


11. (
    괄호 상태: (( (
    시각화:

    ---
    -----
    -------

    cnt = 3, sum_cnt = 7


12. )
    괄호 상태: ((
    시각화:

    ---
    -----

    cnt = 2, sum_cnt += 2 → sum_cnt = 9
    이유: 레이저 → 2개 막대 잘림



---

13. )
    괄호 상태: (
    시각화:

    ---

    cnt = 1, sum_cnt++ → sum_cnt = 10
    이유: 막대 끝 → 마지막 조각 1개


14. (
    괄호 상태: ((
    시각화:

    ---
    -----

    cnt = 2, sum_cnt = 10


15. )
    괄호 상태: (
    시각화:

    ---

    cnt = 1, sum_cnt += 1 → sum_cnt = 11
    이유: 레이저 → 1개 막대 잘림


16. )
    괄호 상태: \`\` (비어있음)
    시각화:

    (없음)

    cnt = 0, sum_cnt++ → sum_cnt = 12
    이유: 마지막 막대 끝 → 마지막 조각 1개

✅ 최종 결과:
sum_cnt = 12

---

🔷 전체코드

arr=input()
cnt=0
sum_cnt=0

for i in range(len(arr)):
    if arr[i]=='(':
        cnt+=1
    else:
        if i>0 and arr[i-1]=='(':
            cnt-=1
            sum_cnt+=cnt
        elif arr[i-1]==')':
            cnt-=1
            sum_cnt+=1

print(sum_cnt)

🔷 결론

• cnt는 현재 열려 있는 쇠막대기의 개수를 나타내며, 여는 괄호에서 증가하고 닫는 괄호에서 감소합니다.
• 레이저(())를 만나면 현재 쌓여있는 쇠막대기의 개수만큼 조각이 늘어납니다.
• 쇠막대기의 끝을 만나면 해당 막대기의 마지막 조각 1개를 더해줍니다.
• 이 과정을 문자열 끝까지 반복하여 최종 조각 수를 구합니다.