hbh1107   5달 전

안녕하세요 2394번 드라이버 투어 문제를 풀던중 막혀서 몇주째 고민하다 게시판에 글올립니다.

소스 코드를 같이 올립니다 조언 주시면 감사하겠습니다.

 

문제 풀이 방식 : KOI 2008 공주구하기 문제와 같은 방식으로 풀었습니다.

DP[a][b]  : 가는 위치가 a이고 오는 위치가 b일때 최대 방문 도시 갯수.

calc(a,b,k) <= 현재 가는 위치가 a에 있고 오는 위치가 b이며 다음 탐색할 위치가 k일때 a,b,k+1 경우, k,b,k + 1경우, a,k,k+1의 경우 중 최댓값으로 갱신했습니다.

 

find_path() 위 calc 함수로 최댓값을 역추적 하기위해서 현재 위치가  a,b일때 다음 이동 지점을 path에 저장했습니다.

 

조언 주시면 정말  감사하겠습니다.

zlzmsrhak   5달 전

메모이제이션 이런식으로 쓸 거면 쓰지 마세요.

1. 21번째 줄에서 memo[a][b]에 값이 있으면 원래 있던 값이 지워집니다.


2. memo 배열의 초기값이 너무 큽니다.

계산 과정에서 언젠가 -1이 리턴되고, 여기에 1이 더해지면서 0 이상의 값인 valid한 값으로 바뀝니다.

반례로, N = 256, N <= 255의 완전그래프를 입력으로 주면 이상한 경로를 출력합니다.


3. 역추적이 잘못됐습니다.

(a, b)가 (2, 4) -> (2, 5) -> (4, 5) 순으로 4가 겹치게 역추적이 될 수 있습니다.

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