7-X 질문있습니다

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-X

해결된 질문

작성

수정됨

int go(int here, int yamyam, int capacity){
	if(here == m) return 0; 
	int &ret = dp[here][yamyam][capacity]; 
	if(ret) return ret;  
        
        ret = max(ret, go(here + 1, yamyam, c)); // <--- 이부분

	for(int i = 0; i < n; i++){  
        bool isbeforeYAM = (1 << i) & yamyam; 
        bool isYAMCAN = (capacity - a[i]) >= 0;
        if(!isbeforeYAM && isYAMCAN)ret = max(ret, go(here, yamyam | (1 << i), capacity - a[i]) + 1);
	}
	return ret; 
}

이 go라는 메소드에서 ret = max(ret, go(here + 1, yamyam, c)); 이 이해가 가지 않습니다.

다음 가방으로 넘어가는데 왜 현재의 (가방, 보석, 용량) 에 값을 저장하나요?

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

일단 이 문제를 보시면

각각의 가방은 C그램의 보석을 담을 수 있다

입니다. 즉, 한가방에 여러개의 보석이 들어갈 수 있습니다.

        if(!isbeforeYAM && isYAMCAN)ret = max(ret, go(here, yamyam | (1 << i), capacity - a[i]) + 1);

여기서 보시면 다음 가방으로 넘어가지 않고 추가를 하는 것을 볼 수 있습니다.

        ret = max(ret, go(here + 1, yamyam, c)); // <--- 이부분

질문하신 부분이 이부분인데요.

로직을 보시면

	for(int i = 0; i < n; i++){  
        bool isbeforeYAM = (1 << i) & yamyam;

다음과 같이 먼저 먹은 보석의 경우 계산하지 않기 위해 -> 해당 값을 넘기는 것입니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

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

tjd125gns님의 질문은 백트래킹에서 상태를 초기화하는 부분에 대한 이해를 돕기 위한 질문으로 보입니다. 문제에서 보석을 가방에 넣지 않기로 결정할 때, 현재의 capacity로 가야 하는 것처럼 보일 수 있지만, 실제로 해당 부분은 새로운 루프나 상태에 들어갈 때 가방의 무게를 초기화하는 역할을 합니다.

요점 설명

ret = max(ret, go(here + 1, yamyam, c)); 부분은 새로운 단계 here + 1로 넘어갈 때 가방의 무게를 최대 용량 c로 리셋시키는 것을 의미합니다. 이는 전체 탐색에서 새로운 상태에서 최적화를 시작할 준비를 하는 동작입니다.
보석을 가방에 넣지 않고 다음 단계로 넘어가는 경우 새로운 시도를 위한 준비 단계로 무게를 초기화합니다.

관련 질문과 답변은 다른 유사한 문제에서 비슷한 패턴으로 다루어진 바 있습니다. 다음의 링크를 참고하시면 추가적인 이해에 도움이 될 수 있습니다:

이러한 설명들은 백트래킹과 관련하여 반복되는 상태 탐색 과정에서 가방의 용량 리셋의 필요성을 이해하는 데 도움을 줄 것입니다.

질문자님의 맥락을 고려하여 설명드렸으며, 내용이 명확하게 전달되었기를 바랍니다. 추가적으로 궁금한 점이 있으시면 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

7-X 질문있습니다

요점 설명