SCPC2016 second freelancer.c

/*
	기본알고리즘 
	Q사를 선택하는것이 P사를 2주 선택하는것이 보다 이득일경우
	Q사를 선택한다.
	2주연속 Q사가 이득일경우 3주중 2주동안 Q사를 선택하고 3주차에 P사를 하는것과
	1주에 P사를 2 3 주에 Q사를 수행하는것중 어떤것이 더이득인지 판별한다. 
*/

#include <stdio.h>
#include<string.h>
#define MAX 10000
int P[MAX],Psum[MAX-1],Q[MAX],res;
char plane[MAX];

void change(int i)
{
	int tmp1,tmp2;
	tmp1=Q[i-1]+P[i];
	tmp2=Q[i]+P[i-2];//Q[i-1]은 i-2와 i-1주를 사용
	//따라서 Q[i-1]를 해제하고 Q[i]할당시 P[i-2]가 남게된다.
	if(tmp2>tmp1)
	{	
		if(plane[i])//금주에 할당되었을경우
			res-=P[i];//할당 반환
		res+=Q[i];//Q선택
		plane[i]=2;//0 no reserved 1 P 2 Q
		res-=Q[i-1];//Q[[i-1]반환
		res+=P[i-2];
		plane[i-2]=1;//Q사대신 P사를 할당
		if(i<=2)return;//i가 2보다 작을경우
		if(Q[i-2]>Psum[i-2])//
		{
			if(plane[i-3]==1)//i-2가P사이므로 i-3도 P사일경우
			{
				res+=Q[i-2];//i-2를 Q사로 할당
				res-=Psum[i-2];//i-2,i-3를 할당 해제
				plane[i-2]=2;//Q사로할당
				plane[i-3]=2;
			}
			else if(plane[i-3]==2)//
			{
				change(i-2);//i-3이 Q사일경우 change를 호출하여 i-3에대해 이익을 판별한다.
			}
		}
		
	}
	else//Q사를 선택하는것이 이익이 아닐경우
	{
		if(!plane[i])
		res+=P[i];
		plane[i]=1;//P사 선택
	}
}
int main(void) {
   	/* 아래 freopen 함수는 sample_input.txt를 read only 형식으로 열고, 표준입력(키보드) 대신 sample_input.txt 로 부터 읽어오겠다는 의미의 코드입니다.
	   만약 본인 PC 에서 테스트 할 때는, 입력값을 sample_input.txt에 저장한 후 freopen 함수를 사용하면
   	   그 아래에서 scanf 함수를 사용하여 표준입력 대신 sample_input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
   	   또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
	   단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야만 합니다. */
	// freopen("sample_input.txt", "r", stdin);

	/* setbuf 함수를 사용하지 않으면, 본인의 프로그램이 제한 '시간 초과'로 강제 종료 되었을 때,
	   printf로 출력한 내용이 채점되지 않고 '0점'이 될 수도 있습니다.
	   시간 초과 전까지 실행된 결과 점수를 받고자 하신다면 "setbuf(stdout, NULL);" 를 사용하시기 바랍니다. */


	int T;
	int test_case,n,i,tmp1,tmp2;
	setbuf(stdout, NULL);
	scanf("%d", &T);
	for(test_case = 1; test_case <= T; test_case++) {
		// 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
        
        memset(P,0,sizeof(P));
		memset(Psum,0,sizeof(Psum));
		memset(Q,0,sizeof(Q));
		memset(plane,0,sizeof(plane));
		res=0;
		//end of initialize.
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%d",&P[i]);
			if(i!=0)
				Psum[i]=P[i-1]+P[i];
		}
		for(i=0;i<n;i++)
			scanf("%d",&Q[i]);
		//end of input
		//1주차//
		if(P[0]<Q[0])//첫주의 Q회사는 1주만에 종료 가능
		{
			res+=Q[0];
			plane[0]=2;//1 P사 2 Q사
		}
		else
		{
			res+=P[0];//P사선택
			plane[0]=1;
		}

		//2주차//
		if(Q[1]>Psum[1])//Q회사의 가치가 P회사 2추치보다 클때
		{
			res+=Q[1];//그리디하게 Q로 선택
			plane[1]=2;//0 no reserved 1 P 2 Q
			if(plane[0]==1)//이미 P사를 선택했었을시
			{
				res-=P[0];//P사취소
				plane[0]=2;//Q사선택
			}
			else if(plane[0]==2)//이전에 Q사를 선택했을때
			{
				tmp1=Q[0]+P[1];//이전에 Q사선택했을시 이번에 Q+P선택
				tmp2=Q[1];//이번에 Q선택시 이익
				if(tmp2>tmp1)//이번에 Q사를 선택하는것이 더 이득일때
				{
					res-=Q[0];//이번의 Q사를 위해2주를 사용하므로 이전 Q값을 뺀다. 
				}
				else
				{
					res-=Q[1];//이번 Q사의 이익을 뺀다
					res+=P[1];//P사를 선택
					plane[1]=1;
				}
			}
			else
			{				
				plane[0]=2;
			}

		}
		else//Q사를 선택하는 이익이 크지 않는다면
		{
			res+=Psum[1];//전주와 이번주 P를 선택한다.	
			plane[1]=1;//P선택			
			if(plane[0])//이전에 P를 선택시
				res-=P[0];//중복 선택되었으므로 한번 빼준다.
			else
				plane[0]=1;
		}


        for(i=2;i<n;i++)
		{
			if(Q[i]>Psum[i])//Q사선택
			{
				if(plane[i-1]==1)//전주에 P사선택했을시
				{
					res-=P[i-1];//전주치 차감
					res+=Q[i];//
					plane[i]=2;	//			
					plane[i-1]=2;//2주를 Q사로 할당
				}
				else if(plane[i-1]==2)//전주에 Q사였을경우
				{
					change(i);
				}

			}
			else
			{
				res+=P[i];//P사선택
				plane[i]=1;	
			}
		}

		// 이 부분에서 정답을 출력하십시오.
		printf("Case #%d\n", test_case);
        printf("%d\n",res);
	}

	return 0;	// 정상종료 시 반드시 0을 리턴해야 합니다.
}