kdr06006   5년 전

dp를썼는데도 시간초과가 나네요 다른 해결방법이 있는건가요?

3587jjh   5년 전

DP의 사용은 맞으나 DFS의 함수의 17번째줄로 인해 계산량이 너무 많습니다

kdr06006   5년 전

@3587jjh

for문말고 다른 방법을 쓰라는 건가요?

3587jjh   5년 전

정의를 이렇게 바꿔보세요.

DFS(index) = index일차부터 시작해서 상담했을때 얻을 수 있는 최대 수익

그러면 아래와 같이 두 경우를 생각할 수 있습니다

1. index일의 상담을 하는 경우

2. index일의 상담을 안하는 경우

그러면 DFS(index)는 두 경우중 더 큰 값이 됩니다

각 경우를 하나의 식으로 표현할 수 있는데, 

예를들어 2번의 경우는 DFS(index + 1)로 표현할 수 있습니다

kdr06006   5년 전

오.. 한번 고쳐보겠습니다 감사합니다!

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