그런데 문제를 조금 달리 생각해보면 각각의 원소를 선택하거나 안하는 상황으로 나눌 수 있습니다. 즉 2^m개의 경우의 수를 가진 탐색으로도 바라볼 수 있다는 것이죠. 따라서 아래와 같은 코드도 가능합니다.
voidallergy4(intcur,longlongselected,intminFood){//cur 범위 벗어난 경우if(cur==m)return;if(best<=minFood)return;if(selected==(1<<n)-1){best=min(best,minFood);return;}//선택 안함allergy4(cur+1,selected,minFood);//선택함allergy4(cur+1,selected|foodlist[cur],minFood+1);}
결과적으로 allergy3의 경우에는 mC1 + mC2 + mC3 + ... + mCm 가지 경우를 도출하고
allergy4의 경우에는 2^m가지 경우를 도출합니다. 따라서 탐색하는 조합의 수는 동일합니다. (mC0을 제외하고...)
제가 궁금한 점은 이 두 함수가 똑같은 답을 도출하느냐는 것입니다.
일단 약간의 차이점은 allergy3의 경우 적어도 한개 이상의 원소를 선택한다는 점이 있는 것 같습니다.
정리하자면 조합의 경우엔 탐색 순서를 고정시켜서
for(int next = cur+1; ...)라는 반복문을 이용하여 코드를 짜고 있습니다. 이 코딩 방식과 선택하는경우, 선택하지 않는 경우로 나누는 코딩방식의 논리적, 결과적 차이점이 있는지 매우 궁금합니다. ^^
8년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
Laplace
ALLERGY 같은 유형의 문제를 보면 기본적으로 음식을 선택하는 조합을 찾게 되는데 아래와 같은 재귀함수를 자주 구축하고 있습니다. for문을 봐주세요~
allergy3(-1, 0, 0)의 형태로 함수를 동작시켜서
0, 1, 2, ...., m-1의 원소들을 선택하는 모든 조합을 탐색합니다.
그런데 문제를 조금 달리 생각해보면 각각의 원소를 선택하거나 안하는 상황으로 나눌 수 있습니다. 즉 2^m개의 경우의 수를 가진 탐색으로도 바라볼 수 있다는 것이죠. 따라서 아래와 같은 코드도 가능합니다.
결과적으로 allergy3의 경우에는 mC1 + mC2 + mC3 + ... + mCm 가지 경우를 도출하고
allergy4의 경우에는 2^m가지 경우를 도출합니다. 따라서 탐색하는 조합의 수는 동일합니다. (mC0을 제외하고...)
제가 궁금한 점은 이 두 함수가 똑같은 답을 도출하느냐는 것입니다.
일단 약간의 차이점은 allergy3의 경우 적어도 한개 이상의 원소를 선택한다는 점이 있는 것 같습니다.
정리하자면 조합의 경우엔 탐색 순서를 고정시켜서
for(int next = cur+1; ...)라는 반복문을 이용하여 코드를 짜고 있습니다. 이 코딩 방식과 선택하는경우, 선택하지 않는 경우로 나누는 코딩방식의 논리적, 결과적 차이점이 있는지 매우 궁금합니다. ^^
8년 전