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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net



스택으로 풀려니 막막해서 그냥 꼴리는데로(?) 풀었는데 어찌하다 보니 분할정복으로 풀게 되었습니다.


인터넷에 검색하면 죄다 스택으로 푼 코드밖에 없어서 혹시 다른 방식으로 푼 코드를 알고 싶으신 분들이 있다면 참고하셔도 좋을 것 같습니다!





+ 추가


기존에 검색하면 볼 수 있는 정석의 풀이는 아래와 같더라구요.



"(" 괄호를 스택에 차례대로 담은 다음에 ")" 가 나올때마다 스택 속의 괄호 개수를 더해주면서 푸는 방식이였고, 검색하면 대부분 이 방식으로 푼 코드들만 존재했습니다.



그런데 전 아래와 같은 방식으로 풀었습니다.





쇠막대기가 만들어질 수 있는 경우라면 재귀 함수를 호출하고, "()" 인 레이저를 발견하면 1를 반환하고, 특정 쇠막대기에서 존재하는 레이저 개수를 모두 구한 다음 그 개수를 함수를 타고 올라오면서 더하는 방식으로 풀었습니다.


우리가 분할정복의 기초라고 할 수 있는 병합정렬과 비슷하다고 생각해서(반으로 계속 쪼개다가 2개가 남은 시점에서 두 수를 비교하여 정렬하고, 정렬된 리스트들을 계속 비교하여 합치면서 하나의 큰 뭉치가 되는 것) 분할정복으로 풀었다고 생각하고 있었는데, 작성해주신 댓글을 보니 아니라는 것을 깨달았습니다...ㅋㅋ



아무튼 검색하면 나오는 기존의 풀이와는 좀 다른, 함수를 이용한 색다른 풀이인듯 하니 한번쯤은 참고해보셔도 좋을 것 같습니다!