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

안녕하세요 bahaha님ㅎㅎ

이는 해당 경우의 수를 완전히 지워버리기 위함입니다.

here == n 까지 도달하면 0이 리턴되고, 시간과 금액은 자연수로 주어지므로, 한 번 끝까지 구해진 경우는 모두 dp값이 0보다 큰 값이 저장될 것 같은데 왜 틀리는지 궁금합니다.

>> 한 번 끝까지 구해진 경우는 모두 dp값이 0보다 큰 값이 저장되기 때문입니다.

근데 어떠한 경우의 수는 계산이 안되어야 합니다.

예를 들어

    ret = -1e6;
    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); 
    return ret; 

끝까지 안가는 경우의 수는 바로 -1e6을 가지게 됩니다.

근데 이를 -1로 해놓는다고 생각해보면..

해당 정점의 수는 -1 그리고 그 이전값들을 기반으로

a[here].pay + ret

이 되므로 만약 그 이전정점이 300정도의 값을 지닌다고 해보면.. 299 따위의 값이 되버립니다.

이 경우의 수는 존재하지 않아야 하는데 말이죠.(끝까지 못가므로...)

그렇다면 이 경우의 수를 완전히 배재하고 싶다면 어떻게 해야할까요? 바로 300에서 굉장히 작은수인 -1e6 정도의 가중치를 줘서 지워버려야 합니다.

안그러면 299따위가 되어버려서 299와 200을 비교하게 되고 계산되지 말아야 할 경우의 수인 299가 답이 될 수도 있게 됩니다.

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

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

감사합니다.

강사 큰돌 올림.