인프런 커뮤니티 질문&답변

안녕하세요 종현님 ㅎㅎ

이 코드는 메모이제이션이 잘못되어있어서 상태값 변경을 하면서 최댓값이 누적이 안된다는 오류가 발생합니다.

예를 들어 앞의 그래프처럼 dp[6]에서 dp[a] + 2와 비교를 해야 하는데 종현님 코드는 정점 + 간선으로 처리하는게 아니라 정점 자체로 계속해서 메모이제이션을 넣기 때문에 해당 부분에서 오류가 생겨서 에러가 발생하는 것 같습니다.

(깨끗한 종이로 그려드리고 싶었는데 지금 입원중이라.. 종이가 저것밖에 없습니다. ㅠ)

또한

DP를 설정할 때 중요한 점은.

dp[][] 라는 배열의 의미를 무엇으로 잡느냐라는 것인데요.

int go(int idx, int sumT, int sumM) {
    if(sumT > K)return -1e9;
    if(idx == N)return sumM;
    int &ret = dp[idx][sumT];
    if(ret != -1)return ret;
    ret = max(ret, go(idx+1, sumT + load[idx].first, sumM + load[idx].second));
    ret = max(ret, go(idx+1, sumT + cycle[idx].first, sumM + cycle[idx].second));
    

여기서 종현님의 dp[][]의 의미는 무엇인가요?

dp[0][0]부터 시작해 sumT이하를 썼을 때 최대의값을 뽑아낸다는 것인가요?

이게 좀.. 모호합니다.

왜냐면 dp[][]의 매개변수 값으로 상태값을 예측해야 하는데

dp[0][0]에는 sumT라는 값이 존재하지 않거든요.

이걸 좀 반대로 tom-bottom으로 하는 거를 추천드립니다. 이게 bottom-up으로 하더라도 dp[a][b]의 의미자체를 a라는 idx에서 b를 가질 때의 최대값으로 놓고 하거든요.

따라서 dp[a][b]의 의미자체를 a라는 idx에서 b를 가질 때의 최대값으로 놓는 것으로 하시는게 더 좋을 것 같습니다.

감사합니다.