algospot FESTIVAL

문제 링크입니다. https://algospot.com/judge/problem/read/FESTIVAL

/*

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다.

이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다.

공연장은 하루 빌리는 데 드는 비용이 매일매일 다릅니다.

때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다.

앞으로 N일 간의 공연장 대여 비용을 알고 있다고 합시다.

이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야할까

*/

#include <iostream>

using namespace std;

 

int main(void)

{

        int test, rent, team; //테스트 케이스 수, 대여할 수 있는 날들의 수, 섭외한 공연 팀의 수

        cin >> test;

        if (test <= 0 || test > 100)

        {

               cout << "1 이상 100 이하여야 합니다" << endl;

               exit(1);

        }

        double *result = new double[test];

        for (int i = 0; i < test; i++)

        {

               cin >> rent >> team;

               if (rent <= 0 || rent > 1000)

               {

                       cout << "대여할 수 있는 날은 1일 이상 1000일 이하여야 합니다" << endl;

                       exit(1);

               }

               if (team > rent || team <= 0 || team > 1000)

               {

                       cout << "섭외한 공연 팀의 수는 대여할 수 있는 날보다 적어야 하고 1팀 이상 1000팀 이하여야 합니다" << endl;

                       exit(1);

               }

               int *arr = new int[rent];

               for (int j = 0; j < rent; j++)

                       cin >> arr[j];

               double min = 1000.00000000; //적당히 큰 숫자

               for (int j = team; j <= rent; j++)

               {

                       int cnt = 0;

                       while (j + cnt <= rent) //범위가 rent를 초과해서는 안되므로

                       {

                              int sum = 0;

                              for (int k = cnt; k < j + cnt; k++)

                                      sum += arr[k];

                              if (min > (double)sum / j)

                                      min = (double)sum / j;

                              cnt++;

                       }

               }

               result[i] = min;

               delete[]arr;

        }

        for (int i = 0; i < test; i++)

               printf("%.8lf\n", result[i]); //10^(-7) 이하의 절대/상대 오차가 있는 답은 정답 처리된다고 하였으므로

        delete[]result;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]