알고리즘 문제 - 알고스팟 FESTIVAL 문제

본 문제는 알고스팟(http://algospot.com/judge/problem/read/FESTIVAL)에 있는 문제입니다.

 

문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.

이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?

예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2}라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이 때 하루 평균 (1+2+3)/3 = 2의 비용이 듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4밖에 되지 않습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N (1 ≤ N ≤ 1000)과 이미 섭외한 공연 팀의 수 L (1 ≤ L ≤ 1000, L ≤ N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다.

출력

입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10^-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

예제 입력

2
6 3
1 2 3 1 2 3 
6 2 
1 2 3 1 2 3

예제 출력

1.75000000000
1.50000000000

저만의 풀이 방법을 소개해보겠습니다.
 
물론 저는 코딩 초보기때문에 속도도 느리고 효율도 떨어질것으로 봅니다.
 
저의 답은 수행시간 2985ms가 걸렸고 총 코드 비트수는 1.5kb입니다.
 
 

  
day의 수 = 6 참가팀의 수 = 3 일 경우
(1, 2, 3, 1, 2, 3) = 각 일별 코스트
 
모든 경우의 수를 써보면
 
3개씩 묶을 때 경우의 수 
(1,2,3), (2,3,1), (3, 1, 2), (1, 2, 3)
 
4개씩 묶을 때 경우의 수
(1, 2, 3, 1), (2, 3, 1, 2), (3, 1, 2, 3)
 
5개씩 묶을 때 경우의 수
(1, 2, 3, 1, 2), (2, 3, 1, 2, 3)
 
6개씩 묶을 때 경우의 수
(1, 2, 3, 1, 2, 3)
 
와 같다. 즉, 3개씩 묶을때는 4개의 경우가 있고 4개씩 묶을때는 3개 5개씩 묶을때는 2개 6개씩 묶을 때는 1개의 경우가 있으므로
 
4+3+2+1=7 총 7가지의 경우가 있음을 알 수 있다.
 
코드는 3개씩, 4개씩, 5개씩, 6개씩 묶을때 for문을 4번 돌리므로 
 
days의 수 - 참가팀의 수 + 1 번을 돌리게 되는것과 같은 뜻이 된다.
 
그리고 3개씩 묶을때는 4개 이고 4개씩 묶을때는 3개 인것으로 보아 계속 1개씩 줄어드므로
 
days의 수 - 참가팀의 수 + blk_step으로 선언하고 blk_step은 처음에 1이었다가 각 한 
 
경우의 수가 끝날때마다 blk_step을 1씩 줄여준다.
 
그리고 (1,2,3), (2,3,1), (3, 1, 2), (1, 2, 3) 으로 보면 배열의 인덱스로 보면 012, 123, 234, 345 처럼 start index가 1씩 늘어나므로
 
한번 끝날 때마다 start intext를 1씩 늘려주고 마지막 인덱스도 1씩 늘려줘야한다. 그리고 for문의 횟수는 x개씩 묶는것에 따라 다르므로 x번 돌려야한다.
 
이와같은 방법으로 모든 경우의 수를 파악하고 평균을 내서 가장 작은 값을 찾아서 출력하면된다.
 
#include <iostream>
//#include <string>
//#include <iomanip>
#include <stdio.h>
 
using namespace std;
 
int main(){
 
        int testcase=0;
        int min=0;
        int days=0;
        int nteam=0;
        int dayCost[1000]={0,};
        int sum=0;
        double min_avg=9999.0;
        double new_avg=9999.0;
        double cout_avg[100]={0.0,};
 
        int step=0;
        int start=0;
        int blk_step=1;
 
        //test case 받아줌
        cin >> testcase;
 
        for(int i=0; i < testcase; i++){
 
                //날짜수와팀갯수받아줌
               scanf("%d", &days);
               scanf("%d", &nteam);
 
 
               for(int j=0; j < days;j++){
 
                       //날짜별비용받아줌.
                       scanf("%d", &dayCost[j]);
 
               }
 
               step = nteam;//팀갯수로스탭시작
               blk_step = 1;
               
               //전라인시작이니까
               for(int n=0; n < days-nteam+1; n++){
 
 
                       //한라인을돌릴때쓰는것이고
                       for(int m=0; m < days-nteam+blk_step; m++){
 
                              //더하는서브블록
                              for(int k=start; k < start+step; k++){
 
                                      sum = sum + dayCost[k];
                                             
                              }
 
                              new_avg = (double)((double)sum/(double)step);//평균내보고
 
                              if(new_avg < min_avg)//작으면갱신해줌
                                      min_avg = new_avg;
 
                              sum = 0;//sum 초기화해줌
 
                              //start 세팅
                              if(start <= days-step){
                                      
                                      start++;
 
                              }
                       
                       }//한라인완료
 
                              start = 0;//start 초기화
                              blk_step=blk_step-1;//블록의전체횟수줄여주고
                              step = step+1;//스탭늘려주고
 
 
               }//전라인완료.
 
               cout_avg[i] = min_avg;
               min_avg = 9999.9;//초기화
 
 
        }
 
        for(int i=0; i < testcase; i++){
 
               printf("%.10f\n", cout_avg[i]);
 
        }
 
 
        return 0;
 
}
 
 
다른분이 푸신 방법을 봤는데
 
첫번째에 (1, 2, 3) (1, 2, 3, 1) (1, 2, 3, 1, 2) (1, 2, 3, 1, 2, 3)
 
두번째에 (2, 3, 1,) (2, 3, 1, 2) (2, 3, 1, 2, 3)
 
세번째에 (3, 1, 2) (3, 1, 2, 3)
 
네번째에 (1, 2, 3)
 
으로 하면 훨씬 빠르고 간결하게 할수있었습니다..