U E D R , A S I H C RSS

Tug Of War/김회영

소스 코드

~cpp 
#include<iostream.h> 
//using namespace std; 
 
bool changeTwoPart(int* right,int* left,int gap,int nPeople); 
void changeTwoElement(int* rightPart,int i,int* leftPart,int j); 
void sort(int* array,int count); 
 
void main() 
{ 
        
		int nCount;
		cin>>nCount;
	
		int nPeople; 
		int* nWeightOfPeople; 
		int* leftPart;
		int* rightPart;
		
		int rightTotal=0; 
        int leftTotal=0; 
		
		int* rightOfTotal=new int[nCount];
		int* leftOfTotal=new int[nCount];

		for(int k=0;k<nCount;k++)
		{
			cin.get();
			cin>>nPeople; 
			
			if(nPeople%2==1) 
			{        
					nPeople++; 
					nWeightOfPeople=new int[nPeople]; 
					for(int a=0;a<nPeople-1;a++) 
							cin>>nWeightOfPeople[a]; 
					nWeightOfPeople[nPeople-1]=0; 
			} 
			else 
			{ 
					nWeightOfPeople=new int[nPeople]; 
					for(int a=0;a<nPeople;a++) 
							cin>>nWeightOfPeople[a]; 
			} 
        
			sort(nWeightOfPeople,nPeople); 
          
			leftPart=new int[nPeople/2]; 
			rightPart=new int[nPeople/2]; 
         
			leftTotal=0;
			rightTotal=0;
         
			for(int j=0;j<nPeople;j++)       
			{        
 
					if(j<nPeople/2) 
					{        
							leftPart[j]=nWeightOfPeople[j]; 
							leftTotal+=leftPart[j]; 
					} 
					else 
					{        
							rightPart[j-nPeople/2]=nWeightOfPeople[j]; 
							rightTotal+=rightPart[j-nPeople/2]; 
					} 
			} 
         
			while(changeTwoPart(rightPart,leftPart,rightTotal-leftTotal,nPeople)) 
			{ 
					leftTotal=0; 
					rightTotal=0; 
 
					for(int i=0;i<nPeople/2;i++) 
							leftTotal+=leftPart[i]; 
         
					for(int j=0;j<nPeople/2;j++) 
					rightTotal+=rightPart[j]; 
                 
			} 
         
			leftOfTotal[k]=leftTotal;
			rightOfTotal[k]=rightTotal;
			//cout<<endl<<leftTotal<<" "<<rightTotal<<endl; 
		}
		
		for(int j=0;j<nCount;j++)
			cout<<endl<<leftOfTotal[j]<<" "<<rightOfTotal[j];

		cout<<endl;
} 
 
bool changeTwoPart(int* right,int* left,int gap,int nPeople) 
{ 
         
        int nTempGap; 
        int nMaxGap=0; 
        int nMaxIndexI=0; 
        int nMaxIndexJ=0; 
 
        for(int i=0;i<(nPeople/2);i++) 
        {        
                for(int j=0;j<(nPeople/2);j++) 
                { 
                        nTempGap= right[i] - left[j] ; 
                        if(nTempGap*2 <= gap && nTempGap>= 0 && nTempGap>nMaxGap) 
                        {        
                                nMaxGap=nTempGap; 
                                nMaxIndexI=i; 
                                nMaxIndexJ=j; 
                        } 
                } 
        } 
         
        if(nMaxGap>0) 
        {        
                changeTwoElement(right,nMaxIndexI,left,nMaxIndexJ); 
                return  true; 
        } 
        return false; 
} 
 
void changeTwoElement(int* rightPart,int i,int* leftPart,int j) 
{ 
        int temp; 
        temp=rightPart[i]; 
        rightPart[i]=leftPart[j]; 
        leftPart[j]=temp; 
 
} 
 
//오름차순으로 정렬을 수행합니다. 
void sort(int* array,int count) 
{        
        for(int i=0;i<count;i++) 
                for(int j=i;j<count;j++) 
                { 
                        if(array[i]>array[j]) 
                                changeTwoElement(array,i,array,j); 
                } 
} 


접근 방식이 굉장히 새로와서 놀랬어요~>__<ㅋ - 이승한
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0941 sec