티스토리 뷰
https://www.acmicpc.net/problem/1013
1013번: Contact
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤
www.acmicpc.net
생각보다 훨씬 시간이 많이 걸린 문제였다.
그냥 문자열을 처음부터 탐색하면서 조건들 걸러내면서 하면 풀리긴 풀릴거같은데 뭔가 코드도 엄청 더러워지고 다른 방법이 있을것 같아서 엄청 고민하다가 다른 분들 코드를 찾아봤는데 학교에서 옛날에 배웠던 Determinstic Finite Automata, DFA) 이런걸 쓴 방법이 있었다.
그런데 오토마타 관련 내용은 솔직히 기억 안나고 그냥 비슷하게 그때그때 상태값을 줘서 최종 상태에 따라 YES 인지 NO 인지 출력하도록 했다.
2,6,7,9 = 종료 상태
'PS' 카테고리의 다른 글
| 백준 1325. 효율적인 해킹 (0) | 2022.12.22 |
|---|---|
| 백준 1027. 고층 건물 (0) | 2022.12.20 |
| 백준 3020. 개똥벌레 (0) | 2022.12.16 |
| 백준 2571. 색종이 - 3 (0) | 2022.12.15 |
| 백준 1038. 감소하는 수 (0) | 2022.12.15 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- priority queue
- Dijkstra
- floyd warshall
- Spring
- Kruskal
- dfs
- Unity
- greedy
- recursion
- Stack
- binary search
- two pointer
- Tree
- 조합
- Implementation
- Python
- db
- CSS
- 이분탐색
- 재귀
- 자료구조
- permutation
- MVC
- C
- back tracking
- BFS
- Brute Force
- graph
- C++
- DP
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함