[백준 10799번] 쇠막대기 (C++)

1. 문제

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

10799번: 쇠막대기

레이저로 쇠막대기를 자른다. 쇠막대기와 레이저가 주어졌을 때 잘려서 나누어진 막대조각의 수를 구하는 문제이다. 이때 주어진조건은 다음과 같다.

• ()는 무조건 레이저를 나타낸다.
• 한 막대의 밑에는 위의 막대보다 긴 막대만 올 수 있다.
• 쌓인 막대의 양끝부분은 겹치지 않는다.

 

2. 풀이

현재의 condition을 유지한 상태로 같은 작업을 반복한다는 점에서 stack의 자료구조가 떠올랐다.