[알고스팟] FESTIVAL - 록 페스티벌 (C++)

문제

 

https://www.algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

풀이

 흔히 종만북이라는 알고리즘 문제 해결 전략 책에서 가장 먼저 나오는 문제. 그 만큼 제출 횟수는 많지만 소수점 출력이 8자리 이상은 되어야해서 틀리는 경우가 많은 듯하다. 첫 문제다 보니 틀리면 상당히 의지가 꺽인다.. ㅠㅠ

 

 가장 먼저 생각난 방법은 역시 모든 경우의 수를 모두 구해보는 부르트 포스 전략이다.

 

 공연장을 대여할 수 있는 날의 수(maxDays)가 최대의 값으로, 섭외된 밴드의 수(numTeam) 부터 시작해 최대값까지 모두 반복문을 돌아본다.

 

 일단은 첫째 날부터 시작하는 경우의 합을  먼저 sum에 저장한 후 최소값과 비교해본다.

그 다음부터는 borrowCost[starIdx-j]를  sum에서 뺴주어 통해 가장 앞의 값을 없애고, borrowCost[starIdx]를 더해주어 다음날 부터 시작하는 경우를 다시 계산을 해준다.이렇게 하면 모든 날의 값을 다시 더해주지 않아도, 계산해둔 값을 다시 이용하여 시간을 절약할 수 있다.

 

 최소값과의 비교를 위해 반복문의 시작 부분에 minCost를 100으로 초기해 주는데, 비용의 최대 값이 100이기 때문에 평균의 최소값도 100이 되기 때문이다.

 

결과: 80ms

 

코드

 

	#include<iostream>
	using namespace std;
	int borrowCost[1000];
	int main(){
	int numTest;
	int maxDays,numTeam;
	double minCost;
	double divResult;
	cin>>numTest;
	for(int i=0; i <numTest ; ++i){
	cin>>maxDays>>numTeam;
	for(int j=0; j<maxDays ; ++j)
	cin>>borrowCost[j];
	minCost = 100; //모든 비용은 100이하이므로 100이 평군의 최대값
	for(int j = numTeam; j<=maxDays ; ++j){
	double sum = 0;
	for(int k=0; k<j ; ++k)
	sum += borrowCost[k]; //일단은 0~j-1까지 더해둠
	divResult = sum/j;
	minCost = minCost < divResult ? minCost: divResult;
	for(int starIdx=j; starIdx< maxDays ; ++starIdx){
	sum -= borrowCost[starIdx-j]; //가장 앞의 수를 빼주고
	sum += borrowCost[starIdx]; //그 뒤 차례의 수를 더해줌
	divResult = sum/j;
	minCost = minCost < divResult ? minCost: divResult;
	}
	}
	printf("%.11f\n",minCost);
	}
	return 0;
	}

view raw FESTIVAL.cpp hosted with ❤ by GitHub