https://www.acmicpc.net/problem/1890
1890번: 점프
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장
www.acmicpc.net
포인터를 쓰거나 했다면 더 메모리를 적게 썼을지도 모르지만,
파이썬에 더 익숙해서 그런지 어떻게 풀어야 좋은 건지 잘 모르겠다..
처음에는 반복문으로 풀었는데 (1, 1)에서 시작하는 경로의 개수만 셀 수가 없어서 결국 dfs처럼 풀었다.
근데 중간에 중복 처리를 안해서 시간 초과가 발생했다.
중복 처리를 안할 경우 답은 나오지만 지수 시간이 걸리기 때문에, 재방문을 하지 않도록 꼭 처리를 해야 하는데,
이 부분이 아직도 잘 이해가 되지 않는다.. 🫤
dfs처럼 visited 배열을 만들어서 방문처리를 하거나, dp 배열을 0으로 초기화시키고 dp 배열이 0이 아닌 경우 방문을 하지 않는 식으로 구현하면 당연히 답이 틀리게 나온다.
그래서 질문글을 봤는데, 재귀호출로 (n, n)에 도달하면 (n, n)에서 (1, 1)로 돌아오면서 경로의 개수를 더해주고 이걸 반환하는 것 같다..
이해를 제대로 한건지 잘 모르겠다.
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 2294번: 동전 2 (0) | 2023.10.05 |
|---|---|
| [백준] 1520번: 내리막 길 (0) | 2023.10.04 |
| [백준] 11048번: 이동하기 (0) | 2023.10.02 |
| [백준] 2632번: 피자판매 (0) | 2023.09.29 |
| [백준] 7453번: 합이 0인 네 정수 (0) | 2023.09.28 |