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

안녕하세요 코린이님 ㅎㅎ

	if(limit-w[num].first>=0) ret =max(ret,check(num+1,value+w[num].second,limit-w[num].first));
	if(limit-b[num].first>=0) ret =max(ret,check(num+1,value+b[num].second,limit-b[num].first));

이렇게 짠 것 때문에 틀린 것 같습니다. DP는 작은 하위문제들의 값을 누적해가면서 글로벌한 해를 만들어나가는 알고리즘입니다.

예를 들어 이런 셈이죠.

a -> b -> c

-> d

라는 그래프가 있을 때

c, d로 갈 때는 b라는 정점에서 누적된 최적해가 있어야 합니다. 그 최적해를 기반으로 c와 d라는 정점으로 가서 DP라는 값이 완성이 됩니다.

이 코드는 얼핏보면 괜찮아 보이지만...

마지막 기저사례를 보면 value들을 쌓아서 마지막에 리턴을 해버리고 있습니다.

int check(int num,int value,int limit){ 
	if(num==n) return value;

이 문제 - DP는

하위1 + 하위2 + 하위3 이렇게 쌓아가면서 최적의 max 값을 만들어야 하는데 코드자체가 가장 마지막함수에서 모든 것을 결정해버리니 그런 해들이 안쌓여서 문제가 되는 것 같습니다.

잠시 다시 예를 들어볼게요 ㅎㅎ

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

코린이님, 질문 주셔서 감사합니다. 하지만 제공된 정보 중에서 직접적으로 코딩 문제나 특정한 프로그래밍 관련 질문에 대한 답변을 제공할 수 있는 내용이 없습니다.

질문하실 때 강의 커뮤니티가 아닌 일반 질문&답변 게시판에 질문을 하시면 강사님이 질문을 확인하시기 어렵습니다. 이런 경우는 강의 관련 내용을 해당 강의의 커뮤니티 질문&답변 게시판에 질문해주시면 강사님께서 확인하시고 답변해 주실 거예요!

해당 사이트 접속이나 코드 검토와 같은 자세한 내용은 강의에 관련된 커뮤니티나 해당 프로그래밍 언어, 알고리즘 포럼을 통해 좀 더 전문적인 도움을 받으시는 것을 추천드립니다.

감사합니다.