반응형
문제 출처 :
https://www.acmicpc.net/problem/3986
알고리즘 분석 :
문제 해결에 필요한 사항
1. Stack
스택을 이용하여 문제를 해결 할 수 있다.
문제에서 요구하는 내용을 정리해보면, A, B가 계속해서 입력되는데
AA로 블럭이 맞춰지면 사라지고, BB로 블럭이 맞춰지면 사라진다.
이때 모든 블럭이 모두 사라질 수 있는가? 라는 문제와 같다.
예를들어보자.
AAABABABAAA는 될까?
AAABABABAAA 에서 AA가 사라지고
ABABABAAA 여기서 AB가 사라질 수 없기에 게임이 종료된다.
ABBAABAABA는 될까?
ABBAABAABA // BB가 사라지고
AAABAABA // AA가 사라지고
ABAABA // AA가 사라지고
ABBA // BB가 사라지고
AA //마지막으로 AA가 사라지며 게임이 종료된다.
이렇게 적으면 감이 올 것인데, 즉 스택으로 문제를 해결 할 수 있게 된다.
소스 코드 :
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 | #include <iostream> #include <cstdio> #include <string> #include <stack> using namespace std; int main() { int n; scanf("%d", &n); int ans = 0; for (int i = 0; i < n; i++) { string str; cin >> str; stack<char> st; int len = str.size(); for (int j = 0; j < len; j++) { if (!st.empty() && st.top() == str[j]) { st.pop(); continue; } st.push(str[j]); } if (st.empty()) ans++; } printf("%d", ans); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[13565번] 침투 (0) | 2017.10.11 |
---|---|
[3273번] 두 수의 합 (0) | 2017.10.11 |
[7785번] 회사에 있는 사람 (0) | 2017.10.10 |
[5525번] IOIOI (0) | 2017.10.10 |
[2688번] 줄어들지 않아 (0) | 2017.10.09 |