2169 로봇 조종하기
-
백준 2169 로봇 조종하기Algorithm/BOJ 2021. 6. 2. 15:30
출처: https://www.acmicpc.net/problem/2169 분류: DP 접근방식 백트래킹 문제 같이 보이지만, n, m이 최대 1000이기 때문에 백트래킹으로 접근하면 시간초과가 납니다. 백트래킹에 복잡도를 생각해봤는데, 한 번 이동마다 최대 3가지 경로로 가지가 쳐지고 위로 이동은 없으니 거꾸로 경우를 줄여 2가지로 잡아도 2^1000 하면 시간초과를 면치 못한다고 생각이 드는데요, 제대로 판단한건지는 잘 모르겠네요... 정확히 아시는 분은 답글 부탁드립니다 🙇🏻♂️ 이 문제는 DP로 접근해서 해결할 수 있는데요, 위로 이동하는 경우는 없으니 맨 윗줄은 1, 1지점부터 오른쪽으로 이동하는 경우가 최선의 경우입니다. for col in 1..