7-V 문제 질문

안녕하세요 준영님 ㅎㅎ

제가 답변드리려고 했는데 잘 생각하셨네요. ㅎㅎ

    ret = -INF;
    ret = max(go(idx+1, sumFee+walk[idx].fee, walk[idx].time), go(idx+1, sumFee+ride[idx].fee, sumTime+ride[idx].time));
    return ret;
}

말씀하신 것 처럼 이부분이 문제입니다.

DP라는 것은 로컬 optimum이 쌓여서 글로벌한 optimum으로 만드는 것이 핵심입니다.

즉, 각 정점은 해당 정점에서의 최적의 해를 담고 있어야 합니다.

그러나 준영님의 코드를 보면

go(idx+1, sumFee+walk[idx].fee, walk[idx].time)
go(idx+1, sumFee+ride[idx].fee, sumTime+ride[idx].time)

이 둘중의 max값을 해당 idx에 담고 있는데요. 얼핏보면 괜찮아보이지만..

이런 예를 생각하면 됩니다.

a -> b -> c -> d

d까지 가서 최대의 값을 가짐 -> c로 감 -> b로 감 -> a로 감.. 이렇게 해서 a가 정상적으로 max값을 출력하게 되지만..

DP배열을 보게 되면

아마 이런식으로 담겨있을 가능성이 높습니다.

dp[a] = 100

dp[b] = 100

dp[c] = 100

dp[d] = 100

즉, 간단한 그래프라면.. 어느정도는 될 거 같은데요. 복잡한 그래프라면 이 DP코드는 DP배열을 온전한 값으로 채우지를 못합니다. 그렇게 채우지를 못하고 해당 DP 배열끼리 비교도 안되구요.

그래서 틀리는 것 같습니다.


    if(_time - a[here]._time >= 0)ret = max(ret, go(here + 1, _time - a[here]._time) + a[here].pay); 
    if(_time - b[here]._time >= 0)ret = max(ret, go(here + 1, _time - b[here]._time) + b[here].pay);

이런식으로 어떠한 가중치를 밖으로 빼서 해당 정점에서의 local optmimum을 만들고 그걸 기반으로 비교하게 만들어야 합니다.

즉.. 이런식으로 쌓이게 만들어야 합니다. 정점을 갈 때 + 가 되는 형식으로요 ㅎㅎ

dp[a] = 20

dp[b] = 50

dp[c] = 80

dp[d] = 100

하지만 나머지 부분이나 코드 구조는 전체적으로 깔끔하고 좋게 잘 짜셨습니다. ㅎㅎ

제가 말씀 드린 부분만 생각하시면 될 거 같아요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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