gomino   8년 전

며칠 째 계속 고민해보고 있는데, DP같긴 한데 DP배열 정의를 어떻게 해야 될지 잘 떠오르지가 않습니다.

dp[i][j] = STR이 i, INT가 j일때 깰 수 있는 퀘스트 갯수 로 두면 i,j가 각각 1000*100이니 슬라이딩 윈도를 써도

시간안에 안돌것같고...

정의를 어떻게 해야할지 감이 안오네요.

도와주시면 감사하겠습니다!

mendou12   8년 전

능력치가 (i,j)일때 깰 수 있는 퀘스트의 수는 일정해여

현재 능력치가 (i,j)이고 예전 능력치가(x,y)이면

능력치가 (i,j)일 떄 꺨 수 있는 퀘스트의 보상 합 - 능력치가 (x,y)일때 깰 수 있는 퀘스트 의 보상 합

은 능력치 변화로 인해 새로 얻은 보상의 합이 되여

그리고 좀 더 생각해 보면

1000*1000짜리 배열 1개로 해결할 수 있을 거에여

gomino   8년 전

@mendou12

감사합니다! 좀 더 고민해보겠습니다^^

alohajihwan   7년 전

혹시 좀더 자세하게 설명 가능하신가요?? ㅠㅠㅠ

어떻게 해야할지 감이 전혀 안잡힙니다..ㅠㅠ

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