w3nk18m   2달 전

DP 이용해서 풀었는데,

제대로 구현한 것 같은데,

자꾸 틀렸다고 나오네요;;;

구현방식은

1) 각 셀에서 들어 올수 있는 모든 경우를 구함 (주변에 나보다 높은 녀석들 찾음)

2) (0,0)부터 시작해서 각 셀의 완료 상태 체크 (자신에게 들어오는 셀의 상태들이 모두 완료 상태면 나도 완료 상태가 됨)

3) 완료 상태가 되면 자신에게 들어올 수 있는 주변 셀에 저장된 경로를 다 더함

4) (N-1, M-1)이 완료 상태가 될 때까지 무한 루프

어떤 부분이 틀린 것인지 알려주시면 감사하겠습니다.

rhaos   2달 전

일단 출발점을 (0,0)이 아닌, (M-1,N-1)에서 시작해서 (0,0)에서 도착하는 것으로 바꿔보는게 좋을듯합니다.

그렇게 하면, 주위 칸들이 계산되었는 지 확인하는과정없이 그대로 재귀호출하면 되겠습니다. (값의 대소값만 비교해서) 

w3nk18m   2달 전

그렇군요, 근데 (N-1,M-1)에서 진행해도 상향식 방법으로 풀수 있는 건가요? 한번 다시 도전해봐야겠군요.

답변 감사드립니다.

그리고, 제가 짠 알고리즘은 문제가 있는 건지, 궁금하네요, 논리적으로로는솔루션이 나오는 것 같던데, 물론 제 나름대로 테스트도 해봤구요, 뭐가 잘못된 건지 모르겠네요,

타임아웃이 안나는 거 보면, 결과값이 틀린거 같긴한데,

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