양의 정수를 원소로 가지는 리스트가 주어졌을때, 그 리스트의 크기가 n/2가 되게 2개의 부분리스트로 분할하되,
정수 합의 차가 최소가 되도록 분할한다.
int* dvdFndMin(int *arr,int idx,int len,int *memo){ int *pt_memoA,*pt_memoB; if(idx>=len){ int *retMemo=(int*)malloc(sizeof(int)*len); for(int i=0; i<len; i++) retMemo[i]=memo[i]; return retMemo; } memo[idx]=1; pt_memoA=dvdFndMin(arr,idx+1,len,memo); memo[idx]=0; pt_memoB=dvdFndMin(arr,idx+1,len,memo); return whatIsMin(pt_memoA,pt_memoB,len,arr); }
whatIsMin은 2개의 부분리스트의 정수의 합의 차가 최소가 되는 포인터를 리턴해 주는 함수인데요..
일단 위 코드만 봤을때,
이런 재귀호출 함수는 단위연산을 잴때 어느걸 기준으로 해야 하나요?
제 생각대로 푼건, 재귀호출 횟수와 그리고 ㄱ부분에 있는 for루프의 반복수를 기준으로 했거든요?
재귀 호출의 횟수는 2+2^(n+1)
저기 위에 있는 for문의 루프는 호출 트리의 마지막 에서만 돌아가니까 2^n*n
그래서 2+2^(n+1)+2^n*n 이 되는건가요? ..졸라느리네요
물어볼 사람이 없으니까 답답합니다 ㅜㅜ
