문제링크 : https://www.acmicpc.net/problem/1662
아이디어
- 스택을 사용하여 (을 사용하면 나오는 위치를 우선 구해놓자
- 재귀함수를 사용해서 (만나면 앞에 숫자에서 곱하기 사용
시간복잡도 계산
- 스택사용해서 괄호 시작 및 끝나는 위치 매핑 : O(S)
- 재귀함수 중 순회 : O(S)
- 총합 : O(S)
자료구조
- 괄호 시작 및 끝나는 위치 계산용 스택 : stack(int)
- 스택안에 들어가는 값 : 각각 문자열 인덱스
- 최대값 : 50 > INT 가능
- 괄호 시작 및 끝나는 위치 기록 : map[60]
- 들어가는 값 : 문자열 인덱스
- 최대값 : 50 > INT 가능
- 압축안된 문자열 길이 rs
- 한번 괄호 쌍에 필요한 문자열 최소 3개
- 그럼 최대 50/3 = 17번이 곱해질수 있음
- 최대 9^17 > long long 사용
코드(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <iostream> #include <stack> #include <string> using namespace std; typedef long long ll; int map[60]; string s; ll recur(int st, int en) { ll rs=0; for(int i=st; i<=en; i++) { // 만약 괄호 만나면 해당 괄호 끝에 해당하는 부분까지 곱해주기 if(s[i] == '(') { // 이전글자 빼주기 rs--; ll preChar = s[i-1]-'0'; rs += preChar * recur(i+1,map[i]-1); // 괄호로 인덱스 이동 i = map[i]; } else { rs++; } } return rs; } int main() { fill(map, map+60, 0); cin >> s; stack<char> st; // 괄호 끝나는 위치 기록함 for(int i=0; i<s.size(); i++) { char ec = s[i]; if(ec == '(') { st.push(i); } else if(ec==')') { int ei = st.top(); st.pop(); // 괄호 끝나는 위치 기록 map[ei] = i; } } cout << recur(0, s.size()-1) << '\n'; return 0; } | cs |
문제유형
- 시뮬레이션 - 스택 압축
- 괄호 통해서 압축하는문제
- 사전에 스택으로, 각각 괄호에서 끝나는 부분 구해놓은 뒤
- 재귀함수 통해서 괄호 나올때마다 계산해주는 문제
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1300 내리막길 (0) | 2021.03.18 |
|---|---|
| 백준 1920 수 찾기 (0) | 2021.03.18 |
| 백준 2304 창고 다각형 (0) | 2021.03.17 |
| 백준 14719 빗물 (0) | 2021.03.17 |
| 백준 14499 주사위 굴리기 (0) | 2021.03.17 |