백준 10799
"첫째 주 배울 내용은 기본 자료구조로 배열, 연결리스트, 스택, 큐, 덱, 문자열(기본)과 정렬입니다.
STL들도 이번주와 다음주에 공부하는게 좋겠습니다."
-방장님 말씀... 메모...
문제 : (https://www.acmicpc.net/problem/10799)
문제는 파이프를 절단했을 때 몇 조각들이 나오는 가의 문제
문제 특이점을 정리해 보면
절단기를 나타내는 패턴 "()" 는 한 파이프 안에서 반드시 나온다.
() 패턴이 나오면 이것은 무조건 절단기 표시이겠다.
백준에서 예제가 아주 좋게 나와있어서 예제를 보면서 풀면 아주 좋은 것 같다.
절단기인지 아닌지는 prev와 curr로 입력값을 저장하고 "()" 패턴을 발견하면 절단기로 생각했다.
절단기일때 파이프를 자르기 때문에 절단기를 만날 때마다 결과 값이 될 파이프의 개수를 계산한다.
입력값을 저장할 prev, curr의 변수
최종값을 저장할 result
절단기로 잘려서 끝난 파이프의 수를 저장하는 nowV
절단기로 잘렸지만 아직 끝나지 않은 파이프의 수를 저장하는 accumV
'(' 인 경우 accumV를 하나 증가시키고
')' 인 경우
절단기인 부분이 아니면, accumV를 하나 감소시키고 nowV를 증가시킨다.
(파이프가 끝난 것을 의미하니까 이후의 계산에서는 빼려고)
절단기인 부분이면, accumV를 하나 감소시키고 결과 값을 갱신한다. 결과값 갱신 후에는 nowV를 초기화.
(절단기 시작부분이 accumV에 더해졌기 때문/ 파이프가 끝난거는 세지 않기 위해서)
예시를 통해 보면
입력값 ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) )
[prev]
x ( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) )
curr ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) )
[절단기인 부분]
( v ( ( ( ( v ( v ) ( ( v ) ( v ) ) ( ( v )
[nowV]
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 1
[accumV]
1 0 1 2 3 4 3 4 3 2 3 4 3 2 3 2 1 0 1 2 1 0
[result]
0 0 0 0 0 0 3 3 6 6 6 6 10 10 10 13 13 13 13 16 16
마지막에 남는 잘린 파이프는 result += nowV로 더해준다.
따라서 결과값은 17이 나온다.
< code >
https://github.com/JangJuMan/2019-winter-PS/blob/master/1_10799.cpp
끝
