personqa   2년 전

안녕하세요. 공주 구하기 문제를 푸는데 백트래킹을 사용하여 풀었습니다. -> 방향의 끝을 찾으면 바로 <- 방향으로

찾는 함수를 호출하는데요, 4% 까지 채점 하고 시간 초과가 떠버리네요. 방식이 잘못 된것일까요..

다른 분들을 보게 되면 DP[][] 2차원 배열을 사용하여 경우의 수를 따지게 되는데 DP[ A ] [ B ] 여기서 A와 B의 값이 의미하는게 

뭔지 이해가 잘 되지 않네요. 처음에서 A 까지 걸리는 경우의 수 ? 돌아올 때 B 까지 걸리는 경우의 수 ? 경우의 수만 따지게 되면

그 한 경로에 대해 스프링 형태에 대해서 체크를 어떻게 해야할지도 잘 모르겠네요.. 

zlzmsrhak   2년 전

백트래킹의 경우 시간복잡도가 최대 O(2^N) 정도이고, 이것은 단순한 커팅 몇가지로는 1초 안에 답을 내는 것이 불가능합니다.

DP[A][B]의 뜻은 1-> -- > A -> ?? -> N -> ?? ->B -> -- -> 1인 경로의 수를 세는 것입니다. (--는 이미 결정된 경로, ??는 이제 결정해야되는 경로)

출발 경로의 처음과 도착 경로의 마지막 부분을 동시에 만들어 나간다는 느낌입니다.

스프링이 약한 경우 출발 경로에서만 사용하면 되고, 강한 경우 A와 B가 같지만 않으면 됩니다.

댓글을 작성하려면 로그인해야 합니다.