[알고스팟] 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

 

코드