티스토리 뷰
https://www.acmicpc.net/problem/15558
15558번: 점프 게임
첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보
www.acmicpc.net
처음에 dfs로 시도하다가 bfs로 푸는게 훨씬 낫겟다는 생각이 들었다.
그런데 뭔가 dfs로 될꺼같아서 오기가 생겨 계속 시도해봤는데 시간초과를 벗어날수 없었다.
결국 bfs로 풀었는데 (걍 진작 bfs로 할걸)
bfs는 메모리 초과 판정을 받았다.
처음에 작성한 코드는 위험한 칸인지를 (칸이 0인지) 판단을 큐에서 빼면서 했기때문에
계산한 다음칸이 0, 즉 위험한 칸이라도 일단 큐에 넣었기 때문에 메모리 초과가 난것 같다.
'PS' 카테고리의 다른 글
| 백준 16948. 데스 나이트 (0) | 2022.02.28 |
|---|---|
| 백준 16928. 뱀과 사다리 게임 (0) | 2022.02.28 |
| 백준 11403. 경로 찾기 (0) | 2022.02.27 |
| 백준 2003. 수들의 합 2 (0) | 2022.02.26 |
| 백준 2018. 수들의 합5 (0) | 2022.02.26 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- two pointer
- 이분탐색
- DP
- 재귀
- binary search
- Python
- permutation
- greedy
- back tracking
- floyd warshall
- recursion
- priority queue
- 조합
- dfs
- Kruskal
- Implementation
- BFS
- Dijkstra
- C
- CSS
- MVC
- C++
- Stack
- Unity
- Brute Force
- Tree
- db
- 자료구조
- Spring
- graph
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함