hazxz   2달 전


행렬곱셈을 이용하여 푸신 분들도 많은 것 같고

저는 dfs + 메모제이션을 사용하였습니다.

특정 공항에서 앞으로 남은 cnt 수를 돌 때 일반 dfs라면 중복되는 경로가 존재하므로 그것을 메모제이션 해두고 사용하였습니다.

시간 복잡도는 N^2K 인거 같습니다.

testCase가 몇개인지 모르겠지만 안돌아갈것 같지는 않은데 25%에서 시간초과가 나네요

얼핏 듣기로는 영원히 여행하는 경로를 빼줘야 한다는 것도 같은데 dfs를 돌때 K가 유한하기 때문에 이 경로가 생기는 것 자체를 이해하지 못하겠습니다.

어떤 식으로 코드를 짜야할까요 ??

ntopia   2달 전

시간복잡도는 맞는데

이 문제는 좀 효율적인 구현을 해야 합니다

확률값과 목적지 둘다 저장하면 털릴 가능성이 있습니다..

그리고 저렇게 그냥 확률을 계산해나가면 정밀도가 급격히 떨어지기도 하고요


여러모로 까다로운 (...) 문제에요

ntopia   2달 전

아 그리고 행렬곱셈으로 풀면 절대 안나옵니다 (...)

hazxz   2달 전

네..저도 이런식으로 코드를 짜본적은 처음입니다 ㅋㅋ 그래서 무지 더럽다고 생각하고 있습니다.

확률을 구하는게 아니라 확률의 끝에 있는 공항을 알아내야 하는 문제이기도 하고..

일단 구현에 있어 좀 더 다듬어보겠습니다

답변 감사합니다.

corea   2달 전

안녕하세요.


글에 서술하신 방향과 다르게, i번 공항에 j번째 도착하는 경로를 생각하시면 더 간편하게 해결하실 수 있을 것 같습니다!

여기서 포인트는 'i번 공항에 j번째 도착하는 경로가 여러개라면, 어떤 것을 선택하는게 좋을까?'에 대한 답입니다.

ntopia   2달 전

dp index를 시작점으로 삼는게 아니라

도착점으로 index를 매기면

도착지점을 따로 저장할 필요가 없겠죠

wlxyzlw   2달 전

ntopia님께서 행렬 곱으로 절대 안나온다고 하셨는데,

정확히는 n*n 끼리 행렬 곱으로는 안나오지만,

다른 행렬곱을 사용하면 나올 수 있습니다.

ntopia   2달 전

헐! 그럴수가!

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