15486번 - 퇴사 2
dp를썼는데도 시간초과가 나네요 다른 해결방법이 있는건가요?
DP의 사용은 맞으나 DFS의 함수의 17번째줄로 인해 계산량이 너무 많습니다
@3587jjh
for문말고 다른 방법을 쓰라는 건가요?
정의를 이렇게 바꿔보세요.
DFS(index) = index일차부터 시작해서 상담했을때 얻을 수 있는 최대 수익
그러면 아래와 같이 두 경우를 생각할 수 있습니다
1. index일의 상담을 하는 경우
2. index일의 상담을 안하는 경우
그러면 DFS(index)는 두 경우중 더 큰 값이 됩니다
각 경우를 하나의 식으로 표현할 수 있는데,
예를들어 2번의 경우는 DFS(index + 1)로 표현할 수 있습니다
오.. 한번 고쳐보겠습니다 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
kdr06006 5년 전
dp를썼는데도 시간초과가 나네요 다른 해결방법이 있는건가요?